1. 시간 복잡도
시간 복잡도
- 알고리즘이나 함수가 실행되는 데 걸리는 시간을 데이터 입력 크기에 따라 분석하는 방법
- 특정 코드가 얼마나 효율적으로 수행되는지 평가
- 주로 Big-O 표기법으로 표현
빅오 표기법 (Big-O Notation)
-
알고리즘이 가장 큰 입력 크기에서 수행되는 최대 시간을 나타냄
-
O(1): 상수 시간 복잡도
- 입력 크기에 관계없이 항상 동일한 시간이 걸리는 경우
-
O(log n): 로그 시간 복잡도
- 입력 크기 n이 커질 때 시간은 그에 따라 조금씩만 증가
-
O(n): 선형 시간 복잡도
- 입력 크기 n에 비례하여 시간이 증가
-
O(n log n): 로그 선형 시간 복잡도
- 데이터 정렬과 같은 연산에서 자주 발생
-
O(n²): 제곱 시간 복잡도
- 각 요소에 대해 다시 모든 요소를 비교할 때 발생
-
O(2^n): 지수 시간 복잡도
- n이 커질수록 시간이 급격히 증가
2. List 연산의 시간 복잡도
- list 내의 모든 요소에 대해 확인해야 하는 연산의 경우 -> O(n)
- list 내의 요소를 바로 도출할 수 있는 연산의 경우 -> O(1)
| 연산 | 시간 복잡도 | 설명 |
|---|---|---|
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)이다. |
del a[i] | O(n) | i에 따라 다르다. 최악의 경우 O(n)이다. |
a.sort() | O(nlogn) | 정렬한다. 팀소트(Timsort)를 사용하며, 최선의 경우 O(n)에도 실행될 수 있다. |
min(a), max(a) | O(n) | 최솟값/최댓값을 계산하기 위해서는 전체를 선형탐색해야 한다. |
a.reverse() | O(n) | 뒤집는다. 리스트는 입력 순서가 유지되므로 뒤집게 되면 입력 순서가 반대로 된다. |
3. Dictionary 연산의 시간 복잡도
- dictionary를 생성 시
key값이 암호화되기 때문에 대부분의 연산이 O(1)의 복잡도를 가짐
| 연산 | 시간 복잡도 | 설명 |
|---|---|---|
len(a) | O(1) | 요소의 개수를 리턴한다. |
a[key] | O(1) | 키를 조회하여 값을 리턴한다. |
a[key] = value | O(1) | 키/값을 삽입한다. |
key in a | O(1) | 딕셔너리에 키가 존재하는지 확인한다 |
출처: 파이썬 알고리즘 인터뷰
잘 먹고 잘 살자