반응형
Contents
코딩 테스트를 하다보면 시간 복잡도를 고려하지 않아서 발생하는 시간 초과 문제에 직면할 때가 있다. 코딩 테스트에서는 리스트(List) 구조를 많이 사용하는데, 리스트에 사용할 수 있는 함수 혹은 주요 연산들의 시간 복잡도가 어느 정도인지 알아보자.
List
연산 | 시간 복잡도 | 설명 |
$\text{len(a)}$ | O(1) | 전체 요소의 개수를 리턴한다. |
$\text{a[i]}$ | O(1) | index $i$의 요소를 가져온다. |
$\text{a[i:j]}$ | O(k) | index $i$부터 $j-1$까지의 길이만큼 $k$개 요소를 가져온다. 객체 $k$개에 대한 조회가 필요하기 때문에 O($k$) |
$\text{element in a}$ | O(n) | 요소가 존재하는지 확인하는 경우 순차 탐색을 해야하기 때문에 $n$만큼 시간이 소요된다. |
$\text{a.count(element)}$ | O(n) | 요소의 개수를 리턴한다. |
$\text{a.index(element)}$ | O(n) | 요소의 index를 리턴한다. |
$\text{a.append(element)}$ | O(1) | 리스트 마지막에 요소를 추가한다. |
$\text{a.pop()}$ | O(1) | 리스트 마지막 요소를 추출한다. Stack 연산. |
$\text{a.pop(0)}$ | O(n) | 리스트 첫 번째 요소를 추출한다. Queue 연산. 이때는 전체 복사가 필요하기 때문에 O($n$)이 소요된다. 이때는 리스트보다는 deque을 사용하는 것을 추천한다. deque을 사용하는 경우 시간 복잡도는 O(1)이 된다. |
$\text{del a[i]}$ | O(n) | 최악의 경우 O($n$). |
$\text{a.sort()}$ | O(n logn) | 최선의 경우 O($n$)까지 가능하다. |
$\text{min(a), max(a)}$ | O(n) | 최솟값/최댓값을 계산하기 위해서는 전체를 선형 탐색하여야 한다. |
$\text{a.reverse()}$ | O(n) | 리스트 배열을 전체적으로 뒤집는다. |
Dictionary
파이썬에서의 딕셔너리는 dict()로 사용하며 Key와 Value로 이루어져 있다. 파이썬의 딕셔너리는 내부적으로 해시 테이블(Hash Table)로 구현되어 있기 때문에, 숫자 뿐만 아니라 문자, 집합까지 모두 Key로 사용이 가능할 뿐만 아니라 시간 복잡도가 O(1)이 된다.
연산 | 시간 복잡도 | 설명 |
$\text{len(a)}$ | O(1) | 요소의 개수를 리턴한다. |
$\text{a[key]}$ | O(1) | 키를 조회하여 값을 리턴한다. |
$\text{a[key] = value}$ | O(1) | 키/값을 삽입한다. |
$\text{key in a}$ | O(1) | 딕셔너리에 키가 존재하는지 확인한다. |
'Python > Algorithm' 카테고리의 다른 글
[프로그래머스] 달리기 경주 - Python (0) | 2023.08.24 |
---|---|
[Algorithm] sort()와 sorted()의 차이점 (2) | 2022.08.18 |
[Python] python에서 pickle file 다루기 (0) | 2022.06.20 |
array와 asarray의 차이 (0) | 2022.05.09 |
빅오, 빅오메가, 빅세타란? (0) | 2022.04.28 |