Language/파이썬
[Python] 파이썬 내장함수 시간복잡도
땅어
2020. 12. 15. 16:59
728x90
300x250
시간복잡도
아래는 자주 등장하는 시간복잡도 표기들이다. 표에서 아래로 갈수록 수행시간이 오래 걸린다.
list
리스트는 배열이다. 그렇기 때문에 사이즈가 커질수록 삽입과 삭제 연산이 비효율적으로 된다. 이럴 땐 차라리 deque를 쓰는 것이 효율적이다.
|
Operation |
Average |
Worst |
|
Copy |
O(n) |
O(n) |
|
Append |
O(1) |
O(1) |
|
Pop last |
O(1) |
O(1) |
|
Pop intermediate |
O(k) |
O(k) |
|
Get item |
O(1) |
O(1) |
|
Set item |
O(1) |
O(1) |
|
Delete item |
O(n) |
O(n) |
|
sort |
O(nlogn) |
O(nlogn) |
|
min,max |
O(n) |
O(n) |
|
len |
O(1) |
O(1) |
collections.deque
deque(double ended queue)는 내부적으로 doubly linked list로 구현되어 있다. 양 끝단에 접근이 가능하다. 하지만 중간 원소에 접근하는 것은 느리다.
|
Operation |
Average |
Worst |
|
Copy |
O(n) |
O(n) |
|
Append |
O(1) |
O(1) |
|
Appendleft |
O(1) |
O(1) |
|
Pop |
O(1) |
O(1) |
|
Popleft |
O(1) |
O(1) |
dict
여기서 말하는 average case는 해시함수가 충돌을 일으키지 않도록 견고하게 설계된 경우를 말한다.
|
Operation |
Average |
Worst |
|
Copy |
O(n) |
O(n) |
|
Get item |
O(1) |
O(n) |
|
Set item |
O(1) |
O(n) |
|
Delete item |
O(1) |
O(n) |
참고
728x90
300x250