[알고리즘] 계산 복잡도(시간 복잡도)란?

출처: https://joshuajangblog.wordpress.com/tag/%EB%B9%85%EC%98%A4-%EA%B3%84%EC%82%B0/

 

1. O (빅 오) 표기법 

• 알고리즘의 대략적인 성능을 표시하는 방법
• 입력 크기 n과 필요한 계산 횟수와의 관계에 주목하는 표현 방법 
• 계산 복잡도는 특별한 언급이 없다면 시간 복잡도를 의미하는 것이지만 본래 계산 복잡도는 시간 복잡도(time complexity), 공간 복잡도(space complexity)로 두가지가 있음 
  • 시간 복잡도 (Time Complexity): 특정한 크기의 입력에 대해서 알고리즘이 소요하는 시간이 얼마나 되는가?
  • 공간 복잡도 (Space Complexity): 특정한 크기의 입력에 대해서 알고리즘이 사용하는 컴퓨터 자원(메모리)이 얼마나 되는가?

 

 

2. O(n) & O(1) 

• 0부터 n까지의 총 합을 구한다고 가정해보자. 두 가지 방법이 있다. 
  • 0+1+2+ ... + n 과 같이 직접 모두 더하는 방법
  •  n(n+1)/2 의 공식을 이용하는 방법
• 첫 번째 방법은 n의 크기에 따라 계산 회수가 달라지므로, O(n)의 시간 복잡도를 갖는다.  
  • O(n): 필요한 계산 회수가 입력 크기 n과 비례할 때
• 두 번째 방법은 n의 크기와 무관하게 덧셈 1회, 곱셈 1회, 나누기 1회를 수행한다. 즉, O(1)의 시간 복잡도를 갖는다.
  • O(1): 필요한 계산 회수가 입력 크기 n과 무관할 때 

 

 

3. 자료형에 따른 시간 복잡도

• List 자료형: 삽입, 제거, 탐색, 포함 여부 확인 모두 O(n)에 해당하는 시간 복잡도를 갖는다.
• Set과 Dictionary: 삽입, 제거, 탐색, 포함 여부 확인 연산에 O(1)의 시간 복잡도를 가지고 있습니다.
• 탐색과 확인이 주로 필요한 연산이라면 Set이나 Dictionary를 사용하는 것이 좋고, 순서와 index에 따른 접근이 필요하다면 List 자료형을 사용하는 것이 좋다. 

Lists

Operation	Example	Big-O	Notes
Index	l[i]	O(1)
Store	I[i] = 0	O(1)
Length	len(l)	O(1)
Append	l.append(2)	O(1)
Pop	l.pop()	O(1)	same as l.pop(-1)
Clear	l.clear()	O(1)	similar to l = []
Slice	l[a:b]	O(b-a)	l[1:5] : O(1) l[:] : O(len(l)-0)=O(N)
Extend	l.extend(...)	O(len(...))	depends only on len of extension
Construction	list(...)	O(len(...))	depends on length of ... iterable
check ==, !=	l1 == l2	O(N)
Insert	l.insert(i, v)	O(N)
Delete	del l[i]	O(N)	depends on i O(N) in worst case
Containment	x in/not in l	O(N)	linearly searches list
Copy	l.copy()	O(N)	Same as l[:] which is O(N)
Remove	l.remove(...)	O(N)
Pop	l.pop(i)	O(N)	O(N-i)
Extreme value	min(l)/max(l)	O(N)	linearly searches list for value
Reverse	l.reverse()	O(N)
Iteration	for v in l	O(N)	Worst : no return/break in loop
Sort	l.sort()	O(NlogN)	key/reverse mostly doesn't change
Multiply	k*l	O(kN)	5*l is O(N): len(l)*l is O(N**2)

Sets

Operation	Example	Big-O	Notes
Length	len(s)	O(1)
Add	s.add(5)	O(1)
Containment	x in/not in s	O(1)	compare to list/tuple - O(N)
Remove	s.remove(..)	O(1)	compare to list/tuple - O(N)
Discard	s.discard(..)	O(1)
Pop	s.pop()	O(1)	popped value "randomly" selected
Clear	s.clear()	O(1)	similar to s = set()
Construction	set(...)	O(len(...))	depends on length of ... iterable
check ==, !=	s != t	O(len(s))	same as len(t); False in O(1) if the lengths are different
<= / <	s <= t	O(len(s))	issubset
>= / >	s >= t	O(len(t))	issuperset s <= t == t >= s
Union	s | t	O(len(s)+len(t))
Intersection	s & t	O(len(s)+len(t))
Difference	s - t	O(len(s)+len(t))
Symmetric Diff	s ^ t	O(len(s)+len(t))
Iteration	for v in s:	O(N)	Worst: no return/break in loop
Copy	s.copy()	O(N)

 

Dictionaries: dict and defaultdict

Operation	Example	Complexity Class	Notes
Index	d[k]	O(1)
Store	d[k] = v	O(1)
Length	len(d)	O(1)
Delete	del d[k]	O(1)
get/set default	d.get(k)	O(1)
Pop	d.pop(k)	O(1)
Pop item	d.popitem()	O(1)	popped item "randomly" selected
Clear	d.clear()	O(1)	similar to s = {} or = dict()
View	d.keys()	O(1)	same for d.values()
Construction	dict(...)	O(len(...))	depends # (key, value) 2-tuples
Iteration	for k in d:	O(N)	all forms: keys, values, items Worst: no return/break in loop