시간 복잡도와 알맞는 알고리즘 선택
■ 일반적 알고리즘의 시간복잡도
| 시간 복잡도 worst | 시간 복잡도 least | |
| for문 1 / while문 1 당== iteration | O(N) | |
| python sorting | O(N*log(N)) |
■ python list
| Operation | Example | Big-O | Notes |
| Index | l[i] | O(1) | |
| Store | l[i] = 0 | O(1) | |
| Length | len(l) | O(1) | |
| Append | l.append(5) | O(1) | |
| Pop | l.pop() | O(1) | l.pop(-1) 과 동일 |
| Clear | l.clear() | O(1) | l = [] 과 유사 |
| Slice | l[a:b] | O(b-a) | l[:] : O(len(l)-0) = O(N) |
| Extend | l.extend(…) | O(len(…)) | 확장 길이에 따라 |
| Construction | list(…) | O(len(…)) | 요소 길이에 따라 |
| check ==, != | l1 == l2 | O(N) | 비교 |
| Insert | ㅣ.insert(i, v) | O(N) | i 위치에 v를 추가 |
| Delete | del l[i] | O(N) | |
| Remove | l.remove(…) | O(N) | |
| Containment | x in/not in l | O(N) | 검색 |
| Copy | l.copy() | O(N) | l[:] 과 동일 - O(N) |
| Pop | l.pop(i) | O(N) | l.pop(0):O(N) |
| Extreme value | min(l)/max(l) | O(N) | 검색 |
| Reverse | l.reverse() | O(N) | 그대로 반대로 |
| Iteration | for v in l: | O(N) | |
| Sort | l.sort() | O(N Log N) | timesort 기반 |
| Multiply | k*l | O(k N) | [1,2,3] * 3 » O(N**2) |
> 양끝단 operation / Search O(1) 제외, 거의 대부분 O(N)
> sorting만 O(N * long(N) )
■ python dictionary
| Operation | Example | Big-O | Notes |
| Index | d[k] | O(1) | |
| Store | d[k] = v | O(1) | |
| Length | len(d) | O(1) | |
| Delete | del d[k] | O(1) | |
| get/setdefault | d.method | O(1) | |
| Pop | d.pop(k) | O(1) | |
| Pop item | d.popitem() | O(1) | |
| Clear | d.clear() | O(1) | s = {} or = dict() 유사 |
| View | d.keys() | O(1) | d.values() 동일 |
| Construction | dict(…) | O(len(…)) | |
| Iteration | for k in d: | O(N) |
> dictionary comprehension / iteration 제외 공간복잡도 포기, 시간 복잡도 O(1)로 만듦
■ 대표 알고리즘 시간복잡도
※효율성 조건 반드시 고려되어야 할 사항
- n의 input에 대해, 목표 1초당 : 1억 ~ 10억번 연산 미만(보수적으로 1억으로 잡는게 안전)
- (1)을 고려시 다음이 만족되어야 함 (1초 기준)
※ log는 log2를 의미
N의 범위 최대 만족 시간복잡도
(1초 기준)n=1000
초당 연산회수n = 100000 (10만)
초당 연산회수500 O(N^3) 10억 ... 2000 O(N^2) 1,000,000 (1백만) ...
10,000,000,000 (100억)100000(10만) O( N*log(N) ) 10,000 (1만) 16,000,000 (1천 6백만) 10000000(1천만) O(N) 1000 100,000 (10만) - O(logN) 대략 10 대략 20
※ 빅O 와 알고리즘 정리표
| 알고리즘 | Big O | 정리 |
| 정렬 - 파이썬 sort 함수 | O(N * log(N)) | - |
| 정렬 - heap | O( log(N) ) : heappush/heappop O(N * log(N)) : 한번에 N개 for문 heap정렬 → 파이썬 경우 heapify는 O(N) |
https://korshika.tistory.com/91 https://korshika.tistory.com/5 |
| 정렬 - 퀵소트 | 평균 O(N * log(N)) 최악 O(N^2) |
https://korshika.tistory.com/39 |
| 정렬 - 계수정렬 | O(N) | https://korshika.tistory.com/41 |
| 탐색 - 이진탐색 | log(N) | https://korshika.tistory.com/96 |
| 탐색 - BFS/DFS | O(N) | https://korshika.tistory.com/43 |
| 탐색 - 다익스트라 | E : 간선 edge V : 노드 vertex O( E * log(E)) ≒ O( E * log(V)) |
https://korshika.tistory.com/73 |
| 탐색 - 크루스칼 | E : 간선 edge V : 노드 vertex O(E * log(E) + log(V)) ∴ 노드 V 많을 시 유리 ≒ O( E * log(E)) |
https://korshika.tistory.com/100 |
| 탐색 - 프림 | V : 노드 vertex ∴ 간선 E 많을 시 유리 O(V^2) |
https://korshika.tistory.com/105 |
| 탐색 - 플로이드와샬 | V : 노드 vertex ∴ 간선 E 많을 시 유리 O(V^3) |
https://korshika.tistory.com/101 |
■ 나동빈 - 이것이 코딩 테스트다 참조
> 범위가 작으면 → for / while loop 2중까지 정도로 해결(3중은 거의 안나옴)
> 10만 단위까지 알고리즘의 경우 n * log(n) 으로 해결
> 100만이상 정도, 이후 높은 단위 for 문 1 iteration에 근접한 알고리즘 선택
: 탐색 알고리즘(BFS / DFS), 그리디, 동적 계획법
참조 :
https://book.algospot.com/estimation.html
알고리즘 문제 해결 전략
4.6 수행 시간 어림짐작하기 주먹구구 법칙 프로그래밍 대회의 시간 제한은 알고리즘의 시간 복잡도가 아니라 프로그램의 수행 시간을 기준으로 합니다. 따라서 어떤 알고리즘이 이 문제를 해결
book.algospot.com
https://data-make.tistory.com/223
[Algorithm] 프로그램 수행 시간 짐작하기
참고글 : [Algorithm] 알고리즘 시간 복잡도 분석 #. 프로그램 수행 시간 짐작하기 ㅇ 시간 복잡도의 분할 상환 분석(amoritzed analysis) - 알고리즘의 시간 복잡도를 항상 반복문의 개수를 세는 것만으
data-make.tistory.com