[파이썬]파이썬 주요 연산 시간복잡도 정리

출처 : 파이썬 알고리즘 인터뷰 

 

#빅오 표기법의 종류

종류	설명
O(1)	입력값이 아무리 커도 실행 시간은 일정하다. 최고의 알고리즘이라 할 수 있다.
O(logn)	여기서부터 실행 시간은 입력값에 영향을 받는다. 그러나 로그는 매우 크 입력값에도 크게 영향을 받지 않는 편이므로 웬만한 n의 크기에 대해서도 매우 견고하다. 대표적으로 이진 검색이 이에 해당한다.
O(n)	입력값만큼 실행 시간에 영향을 받으며, 알고리즘을 수행하는 데 걸리는 시간은 입력값에 비례한다. 이러한 알고리즘을 선형 시간 알고리즘이라고 한다. 정렬되지 않은 리스트에서 최대값 또는 최솟값을 찾는 경우가 이에 해당한다.
O(nlogn)	병합정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘이 이에 해당한다. 입력값이 최선인 경우 비교를 건너뛰어 O(n)이 될수도 있으며 팀소트가 이런 로직을 갖고있다.
O(n^2)	버블 정렬 같은 비효율적인 정렬 알고리즘이 이에 해당한다.
O(2^n)	피보나치 수를 재귀로 계산하는 알고리즘이 이에 해당한다. 수가 커질수록 n^2보다 2^n이 더 크다.
O(n!)	각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제를 브루트 포스로 풀이할 때가 이에 해당하며 가장 느린 알고리즘에 해당한다.

 

 

#파이썬 리스트의 주요 연산 시간복잡도 

연산	시간 복잡도	설명
len(a)	O(1)	전체 요소의 개수를 리턴한다.
a[i]	O(1)	인덱스 i의 요소를 가져온다.
a[i:j]	O(k)	i부터 j까지 슬라이스 길이만큼의 k개 요소를 가져옴. 이 경우 객체 k개에 대한 조회가 필요하므로 O(k)이다.
elem in a	O(n)	elem 요소가 존재하는지 확인한다. 처음부터 순차 탐색하므로 n만큼 시간이 소요된다.
a.count(elem)	O(n)	elem요소의 개수를 리턴한다.
a.index(elem)	O(n)	elem요소의 인덱스를 리턴한다.
a.append(elem)	O(1)	리스트 마지막에 elem요소를 추가한다.
a.pop()	O(1)	리스트 마지막 요소를 추출한다. 스택의 연산이다.
a.pop(0)	O(n)	리스트 첫번재 요소를 추출한다. 큐의 연산이다.  이 경우 전체 복사가 필요하므로 O(n)이다. 큐의 연산을 주로 사용한다면 리스트보다는 O(1)에 가능한 데크(deque)를 권장한다.
del a[i]	O(n)	i에 따라 다르다. 최악의 경우 O(n)이다.
a.sort(). b=sorted(a)	O(nlogn)	정렬한다. 팀소트(Timsort)를 사용하며, 최선의 경우 O(n)에도 실행될 수 있다.
min(a), max(a)	O(n)	최솟값/최댓값을 계산하기 위해서는 전체를 선형 탐색해야 한다.
a.reverse()	O(n)	뒤집는다. 리스트는 입력 순서가 유지되므로 뒤집게 되면 입력 순서가 반대로 된다.

 

#파이썬 딕셔너리의 주요 연산 시간 복잡도 

연산	시간 복잡도	설명
len(a)	O(1)	요소의 개수를 리턴한다.
a[key]	O(1)	키를 조회하여 값을 리턴한다.
a[key]=value	O(1)	키/값을 삽입한다.
key in a	O(1)	딕셔너리에 키가 존재하는지 확인한다.