자료구조 & 알고리즘
Python : 시간 복잡도
머기조
2023. 3. 6. 11:22
<Python 사용 시의 '자료형', '연산자', '메소드'에 따른 시간 복잡도 정리>
Python에서는 초당 2,000만 회의 연산이 가능하다고 가정
Pypy3 사용 시, 동일 시간에 더 많은 연산이 가능하지만(빠르지만), 코딩테스트 진행 시 사용이 제한될 수도 있으므로 Python3 제출을 기준으로 학습하는 것이 좋음
빅오(Big-O) 표기법에 대하여
연산 시간의 복잡한 정도를 빅오(Big-O) 표기법으로 나열
: O(1) < O(log(n)) < O(n) < O(nlog(n)) < O(n^2) < O(2^n) < O(N!)
단순하게 생각해서,
print()를 N번 반복하는 코드가 있다고 하자. print()를 동작하는 것은 상수 시간만큼 걸린다. 즉, O(1)의 시간.
이를 N번 반복하면 -> O(1) * N 이라고 생각할 수 있다. 즉, 이러한 경우에는 O(N) 만큼의 시간이 걸리는 것.
겉보기에 단순한 코드도 이중으로 반복 동작을 하게 되면, O(N^2)의 아주 복잡한 수준의 시간이 걸리게 된다.
상대적으로 느린 시간을 자랑하는 파이썬으로 알고리즘을 풀이하는 경우, 이는 치명적일 수 있다.
Python 자료형에 따른 연산자 시간 복잡도
리스트(list) / 튜플(tuple)
집합(set)
딕셔너리(dict)
