시간복잡도(Big-O) 란?
- 알고리즘의 효율성을 표기해주는 표기법
- 입력값이 무한대로 향할 때 함수의 상한을 설명한다.
- ( ) 안의 값은 최고차항만 표기한 것
ex. 4n^2 + 3n + 4 => O(n^2) - k는 매개변수 값이거나 매개변수의 원소 수를 의미한다.
빅오 표기법의 종류
O(1): 입력값에 상관없이 일정한 실행시간 (최고의 알고리즘)O(log n): 로그는 매우 큰 입력값에도 크게 영향을 받지 않는 편이다. 이진 탐색의 경우가 이에 해당한다.O(n): 실행시간이 입력값에 비례한다. 선형 시간 알고리즘이라 부른다. 정렬되지 않은 리스트에서 최대 또는 최솟값을 찾는 경우가 해당되며 모든 입력값을 적어도 한 번 이상 살펴봐야한다.O(n log n): 병합, 정렬 등의 대부분 효율이 좋은 알고리즘이 이에 해당한다. 아무리 좋은 알고리즘이라 할지라도 n log n보다 빠를 수 없다. 입력값이 최선일 경우, 비교를 건너뛰어 O(n)이 될 수 있다.O(n^2): 버블 정렬 같은 비효율적인 정렬 알고리즘이 이에 해당한다.O(2^n): 피보나치의 수를 재귀로 계산하는 알고리즘이 이에 해당한다. n^2보다 훨씬 크다.
list
| Operation | Big-O | Notes |
|---|---|---|
| Index | O(1) | l[i] |
| Store | O(1) | l[i] = 0 |
| Length | O(1) | len(l) |
| Append | O(1) | |
| Pop | O(1) | l.pop(-1) 과 동일 |
| Clear | O(1) | l.clear(), l = [] 과 유사 |
| Slice | O(b-a) | l[a:b] |
| Extend | O(len(k)) | l.extend(k) |
| Construction | O(len(k)) | list(k) |
| check | O(N) | ==, != |
| Insert | O(N) | l.insert(i, v): i 위치에 v를 추가 |
| Delete | O(N) | |
| Remove | O(N) | |
| Containment | O(N) | x in/not in l |
| Copy | O(N) | l[:] 과 동일 |
| Pop | O(N) | l.pop(0)도 O(N) |
| Min/Max | O(N) | |
| Reverse | O(N) | |
| Loop | O(N) | |
| Sort | O(N Log N) | |
| Multiply | O(k N) |
Dict
| Operation | Big-O | Notes |
|---|---|---|
| Index | O(1) | |
| Store | O(1) | |
| Length | O(1) | |
| Delete | O(1) | |
| Get / Setdefault | O(1) | 사전기본값 처리 |
| Pop | O(1) | |
| Pop item | O(1) | d.popitem() |
| Clear | O(1) | s = {} or = dict()와 유사 |
| View | O(1) | .keys(), .values() |
| Construction | O(len(…)) | dict(…) |
| Iteration | O(N) | for k in d: |
Deque
| Operation | Big-O | Notes |
|---|---|---|
| copy | O(n) | |
| append | O(1) | |
| appendleft | O(1) | |
| pop | O(1) | |
| popleft | O(1) | |
| extend | O(k) | a.extend(k) |
| extendleft | O(k) | |
| rotate | O(|k|) | k<0:반시계, k>0:시계 |
| remove | O(n) |
