시간 복잡도와 알맞는 알고리즘 선택

■ 일반적 알고리즘의 시간복잡도

	시간 복잡도 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)로 만듦

 

 

■ 대표 알고리즘 시간복잡도

※효율성 조건 반드시 고려되어야 할 사항

1. n의 input에 대해, 목표 1초당 : 1억 ~ 10억번 연산 미만(보수적으로 1억으로 잡는게 안전)
2. (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

알고리즘 문제 해결 전략

https://data-make.tistory.com/223

[Algorithm] 프로그램 수행 시간 짐작하기