최근 사고력의 향상을 위해서 꾸준하게 알고리즘 문제를 풀어보고 있다. 당연 필자가 가장 자신있는 언어라고 생각하는 파이썬을 응용하고 있는데 시간초과가 생각보다 많이 발생했다. O(1)로 접근할 수 있는 요소를 O(n)으로 접근하는 등 기본기의 부족으로 인함으로 보였다. 이런 문제를 개선해서 정답처리 된 문제도 있었고… 그리하여 파이썬의 각 자료형의 연산에 대한 복잡도를 완벽하게 숙지해 놓으려고 한다.

출처 : https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt


리스트

자료형 리스트의 각 연산별 복잡도

O(1)
연산자 예시 주석
Index my_list[i] 연결 리스트라 O(1)이 아닐거라 생각했다. 그래서 일부러 딕셔너리로 해결한적도 많았는데… 파이썬을 너무 얕본 듯 하다.
Store my_list[i] = 0 이하 동문…
Length len(my_list) 내부적으로 길이 변수를 가지고 있는 듯 하다.
Append my_list.append(x)  
Pop my_list.pop()  
Clear my_list.clear() my_list = [] 와 같다.
O(N)
연산자 예시 주석
Check my_list1 == my_list2  
Insert my_list[a:b] = …  
Delete del my_list[x] 이거 O(N) 이었다고?!?!
Containment x in my_list  
Copy my_list.copy()  
Remove my_list.remove(x)  
Pop my_list.pop(x) 정확히는 N-x 만큼의 복잡도가 걸린다.
Extream value my_list.reverse()  
Iteration for x in my_list breakreturn이 없는 경우 최악
O(?)
연산자 예시 복잡도 주석
Slice my_list[a:b] O(b-a)  
Extend my_list.extend(…) O(len(…))  
Construction list(…) O(len(…))  
Sort my_list.sort() O(N Log N) 키/역순은 영향을 주지 않는다.
Multiply x*my_list O(k N)  


집합

자료형 집합의 각 연산별 복잡도

O(1)
연산자 예시 주석
Length len(my_set)  
Add my_set.add(5)  
Containment x in my_set  
Remove my_set.remove(…)  
Discard my_set.discard(…)  
Pop my_set.pop()  
Clear my_set.clear() my_set = set()과 같다.
O(N)
연산자 예시 주석
Iteration for x in my_list breakreturn이 없는 경우 최악
Copy my_list.copy()  
O(?)
연산자 예시 복잡도 주석
Construction set(…) O(len(…))  
Check s != t O(len(s))  
<= / < s <= t O(len(s))  
>= / > s >= t O(len(t))  
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))  


딕셔너리

자료형 딕셔너리의 각 연산별 복잡도

O(1)
연산자 예시 주석
Index my_dict[k]  
Store my_dict[k] = v  
Length len(my_dict[k])  
Delete del my_dict[k]  
Get / Set my_dict.get(k)  
Pop my_dict.pop(k)  
Pop item my_dict.popitem()  
Celar my_dict.clear() my_dict = dict()와 같다.
View my_dict.keys() my_dict.values()와 같다.
O(N)
연산자 예시 주석
Iteration for key in my_dict all forms: keys, values, items
O(?)
연산자 예시 복잡도 주석
Construction dict(…) O(len(…))  

앞으로 문제를 풀때는 최대한 이 표를 기억하며 O(1)의 연산자로 풀이할 방안을 찾도록 해야겠다. 😅

WRITTEN BY

배진오

소비적인 일보단 생산적인 일을 추구하며, 좋아하는 일을 잘하고 싶어합니다 :D
im@baejino.com