출처: 파이썬 알고리즘 인터뷰 (박상길 저)
| 연산 | 시간 복잡도 | 설명 |
|---|---|---|
len(a) | O(1) | 전체 요소의 개수를 리턴한다. |
a[i] | O(1) | 인덱스 i의 요소를 가져온다. |
a[i:j] | O(k) | 인덱스 i부터 j-1까지 슬라이스의 길이만큼인 k개의 요소를 가져온다. 이 경우 객체 k개에 대한 조회가 필요하므로 O(k)이다. |
elem in a | O(n) | elem 요소가 존재하는지 확인한다. 처음부터 순차 탐색하므로 n만큼 시간이 소요된다. |
a.count(elem) | O(n) | elem 요소의 개수를 리턴한다. |
a.index(elem) | O(n) | elem 요소의 인덱스를 리턴한다. |
a.append(elem) | O(1) | 리스트 마지막에 elem 요소를 추가한다. |
a.pop() | O(1) | 리스트 마지막 요소를 추출한다. 스택의 연산이다. |
a.pop(0) | O(n) | 리스트 첫번째 요소를 추출한다. 큐의 연산이다. 이 경우 전체 복사가 필요하므로 O(n)이다. 큐의 연산을 주로 사용한다면 리스트보다는 O(1)에 가능한 데크(deque)를 권장한다. |
del a[i] | O(n) | i에 따라 다르다. 최악의 경우 O(n)이다. |
a.sort() | O(NlogN) | 정렬한다. 팀소트(Timsort)를 사용하며, 최선의 경우 O(n)에도 실행될 수 있다. |
min(a), max(a) | O(n) | 최솟값/최댓값을 계산하기 위해서는 전체를 선형 탐색해야 한다. |
a.reverse() | O(n) | 뒤집는다. 리스트는 입력 순서가 유지되므로 뒤집게 되면 입력 순서가 반대로 된다. |
코뉴의 도딩기록