Python : len(a)는 O(1)이죠? 그리고 a.append는 O(n)인가요?
2170
points
points
a라는 리스트가 있으면
len(a)는 당연히 O(1)이겠죠?
그런데 루프 안에서 len(a)를 부르는 것이 루프 밖에서 lena=len(a)로 저장해 두는 것과 비교했을 때 오버헤드가 발생할까요?
그리고 a.append(b)는 O(n)인가요? 아니면 O(1)인가요.
O(n)이라면 a.insert(0, b)로 루프를 돌리는 것과 a.append(b)로 루프를 돌린뒤에 a.reverse()를 했을 때의 차이가 있을까요?
append가 만약에 O(1)이면 append를 쓰는게 낫겠지만 세상이 그렇게 호락호락 하지 않을 것 같네요.
그 외에도 Python의 실행 시간과 관련해서 도움이 될만한 레퍼런스가 있다면 소개 부탁드립니다.
points
O(1) 이겠지만...
Python의 list는 C++의 vector와 유사하게 작성되었다고 기억합니다.
뭐, 만일 deque와 유사하게 작성되었다면 insert(0, b)나 append나
동일한 시간복잡도가 나오기야 하겠지요.
그런데 Python을 가지고 그렇게 시간을 철저히 따져야할 작업을 하고 계신건가요?
이미 시간이 너무 들어서 최적화를 염두하고 계신 것이 아니라면 너무 머리
아프게 살지 마시고, 편한데로 하심이 좋을 듯...
열라 오래된 문서지만 파이썬 문서고의
http://coreapython.hosting.paran.com/etc/Python%20Performance%20Tips.htm
http://coreapython.hosting.paran.com/etc/optimization%20anecdote.htm
읽어보시길...
points
감사합니다. Just for
감사합니다. Just for fun입니다. ;)
# emerge girl-friend
Calculating dependencies
!!! All wemen who could satisfy "girl-friend" have been masked.
points
정확히는 모르겠는데
Python 의 list 는 array of pointers 로 알고 있습니다.
그래서 len(a) 는 O(1) 이니 오버헤드의 면으론 차이가 없을 겁니다.
리스트 뒤에 붙이는건 O(1) ( amortized O(1) ) 일 겁니다.
앞에 붙이는 건 O(n) 이구요.
그리고 둘의 비교는 아마도 후자가 더 빠를 것 같습니다.
a.reverse() 가 아마 O(n) 일 겁니다.
그리고 Python 엔 deque 가 따로 있습니다 (collections.deque).
이건 앞뒤 붙이는 것 모두 O(1) 이겠지만 오버헤드가 더 있고
search 가 O(n) 일거라 생각됩니다.