코딩하는 해맑은 거북이
[Python] 내장함수 시간복잡도 본문
해당 글은 아래의 3가지를 다룬다.
📌 List
📌 collections.deque
📌 Dict
📌 List
- 파이썬의 정렬 함수는 병합 정렬과 삽입 정렬의 아이디어를 더한 하이브리드 방식의 정렬 알고리즘을 사용하고 있다.
병합 정렬은 퀵 정렬보다 느리지만, 최악의 경우에도 O(nlogn)의 시간 복잡도를 보장한다는 특징이 있다.
- List는 크기가 커질수록, 삽입과 삭제 연산이 비효율적으로 된다. 그럴 경우에는 deque를 사용하는 것이 효율적이다.
cf) 코딩테스트 시 문제에 별도의 요구가 없다면, 기본 정렬 알고리즘을 사용하고
데이터의 범위가 한정되어 있고 더 빠르게 동작해야 할 때는 계수 정렬을 사용해야 한다.
| 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) |
| insert | O(n) | O(n) |
| Get item | O(1) | O(1) |
| Set item | O(1) | O(1) |
| Delete item | O(n)` | O(n) |
| Iteration | O(n) | O(n) |
| Get Slice | O(k) | O(k) |
| Del Slice | O(n) | O(n) |
| Set Slice | O(k+n) | O(k+n) |
| extend | O(k) | O(k) |
| sort | O(nlogn) | O(nlogn) |
| Multiply | O(nk) | O(nk) |
| min, max | O(n) | O(n) |
| len | O(1) | O(1) |
📌 collections.deque
Collections 라이브러리의 deque 함수는 내부적으로 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) |
| extend | O(k) | O(k) |
| extendleft | O(k) | O(k) |
| rotate | O(k) | O(k) |
| remove | O(n) | O(n) |
📌 Dict
여기서 말하는 평균 케이스는 해시함수가 충돌을 일으키지 않도록 견고하게 설계된 경우를 의미한다.
| 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) |
| Iteration | O(n) | O(n) |
[참고자료]
https://daimhada.tistory.com/56
Python 내장 함수의 시간 복잡도
Python 컨테이너 메소드의 시간 복잡도(time complexity)는 어떻게 될까? 알고리즘을 풀면서 컨테이너를 조작하기 위해 기본 메소드들을 많이 활용하게 되었고, 메소드의 시간 복잡도가 궁금해졌다.경
daimhada.tistory.com
'Python > 기본' 카테고리의 다른 글
| [Python] 비트 연산자 종류 (0) | 2024.01.09 |
|---|---|
| [Python] all 함수, any 함수 (0) | 2023.12.09 |
| [Python] 시간복잡도, 공간복잡도 제한 (0) | 2023.08.18 |
| [Python] math 라이브러리 주요 함수 (0) | 2023.06.15 |
| [Python] for if-else 한줄로 작성하는 방법 (0) | 2023.06.14 |
Comments