알고리즘의 시간 복잡도(Time Complexity)는 알고리즘의 성능을 평가하는 중요한 개념 중 하나이다. 이는 입력 크기(input size)에 따라 알고리즘이 실행되는 시간의 증가율을 나타내고, 시간 복잡도는 보통 Big-O 표기법(Big-O Notation)으로 표현된다.
-
시간 복잡도의 의미
시간 복잡도는 알고리즘의 효율성을 비교하고 평가하는 데 사용되는데, 시간 복잡도를 이용해 다음과 같은 질문에 답할 수 있다:
- 입력 크기가 커질 때, 알고리즘의 실행 시간이 어떻게 변하는가?
- 주어진 입력 크기에 대해 알고리즘이 얼마나 빨리 실행될 수 있는가?
-
Big-O 표기법
Big-O 표기법은 알고리즘의 실행 시간이 입력 크기에 따라 어떻게 증가하는지를 나타내는 표기법이다. 이는 최악의 경우(가장 비효율적인 경우)에 대한 실행 시간을 표현할 수 있다.
시간복잡도의 문제해결 단계
- O(1): 상수 시간 : 문제를 해결하는데 오직 한 단계만 처리함.
- O(log n): 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬.
- O(n): 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐.
- O(n log n): 문제를 해결하기 위한 단계의 수가 N*(log2N) 번만큼의 수행시간을 가진다. (선형로그형)
- O(n^2): 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱.
- O(C^n): 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱.
시간복잡도 구하기
- 하나의 루프를 사용하여 단일 요소 집합을 반복 하는 경우: O (n)
- 컬렉션의 절반 이상 을 반복 하는 경우: O (n / 2) -> O (n)
- 두 개의 다른 루프를 사용하여 두 개의 개별 콜렉션을 반복 할 경우: O (n + m) -> O (n)
- 두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우: O (n²)
- 두 개의 중첩 루프를 사용하여 두 개의 다른 콜렉션을 반복 할 경우: O (n * m) -> O (n²)
- 컬렉션 정렬을 사용하는 경우: O(n*log(n))
정렬 알고리즘 비교
| Sorting Algorithms |
공간 복잡도 |
시간 복잡도 |
| |
최악 |
최선 |
평균 |
최악 |
| Bubble Sort |
O(1) |
O(n) |
O(n2) |
O(n2) |
| Heapsort |
O(1) |
O(n log n) |
O(n log n) |
O(n log n) |
| Insertion Sort |
O(1) |
O(n) |
O(n2) |
O(n2) |
| Mergesort |
O(n) |
O(n log n) |
O(n log n) |
O(n log n) |
| Quicksort |
O(log n) |
O(n log n) |
O(n log n) |
O(n2) |
| Selection Sort |
O(1) |
O(n2) |
O(n2) |
O(n2) |
| Shell Sort |
O(1) |
O(n) |
O(n log n2) |
O(n log n2) |
| Smooth Sort |
O(1) |
O(n) |
O(n log n) |
O(n log n) |
자료구조 비교
| Data Structures |
Average Case |
Worst Case |
| |
Search |
Insert |
Delete |
Search |
Insert |
Delete |
| Array |
O(n) |
N/A |
N/A |
O(n) |
N/A |
N/A |
| Sorted Array |
O(log n) |
O(n) |
O(n) |
O(log n) |
O(n) |
O(n) |
| Linked List |
O(n) |
O(1) |
O(1) |
O(n) |
O(1) |
O(1) |
| Doubly Linked List |
O(n) |
O(1) |
O(1) |
O(n) |
O(1) |
O(1) |
| Stack |
O(n) |
O(1) |
O(1) |
O(n) |
O(1) |
O(1) |
| Hash table |
O(1) |
O(1) |
O(1) |
O(n) |
O(n) |
O(n) |
| Binary Search Tree |
O(log n) |
O(log n) |
O(log n) |
O(n) |
O(n) |
O(n) |
| B-Tree |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
| Red-Black tree |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
| AVL Tree |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
자료형 별 함수의 시간복잡도
| 리스트(List) |
- 순서 O, 수정 가능(mutable) |
list = [v1, v2, …] |
| 세트(Set) |
- 순서 X, unique, mutable |
set = {v1, v2, …} |
| 딕셔너리(Dictionary) |
- 순서 X, 키(immutable), 값(mutable)이 맵핑 |
dict = {k1:v1, k2:v2, …} |
list 메소드 별 시간복잡도
| Operation |
Example |
Big-O |
Notes |
| Index |
l[i] |
O(1) |
인덱스로 값 찾기 |
| Store |
l[i] = val |
O(1) |
인덱스로 데이터 저장 |
| Length |
len(l) |
O(1) |
리스트 길이 |
| Append |
l.append(val) |
O(1) |
리스트 뒤에 데이터 추가 |
| Pop |
l.pop() |
O(1) |
리스트 마지막 데이터 pop |
| Clear |
l.clear() |
O(1) |
빈 리스트로 만듬 |
| Slice |
l[a:b] |
O(b-a) |
슬라이싱 |
| Extend |
l.extend(l2) |
O(len(l2)) |
리스트 확장 |
| Construction |
list(…) |
O(len(…)) |
리스트 생성 |
| check ==, != |
l1 == l2 |
O(N) |
|
| Insert |
l[a:b] = … |
O(N) |
데이터 삽입 |
| Delete |
del l[i] |
O(N) |
데이터 삭제 |
| Containment |
x in/not in l |
O(N) |
x값 포함 여부 확인 |
| Copy |
l.copy() |
O(N) |
리스트 복제 |
| Remove |
l.remove(val) |
O(N) |
리스트에서 val값 제거 |
| Pop 2 |
l.pop(i) |
O(N) |
i번째 인덱스 값 pop |
| Extreme value |
min(l) / max(l) |
O(N) |
전체 데이터를 체크해야함 |
| Reverse |
l.reverse() |
O(N) |
뒤집기 |
| Iteration |
for v in l: |
O(N) |
|
| Sort |
l.sort() |
O(N log N) |
파이썬 기본 정렬 |
| Multiply |
k*l |
O(k N) |
|
set 메소드 별 시간복잡도
| Operation |
Example |
Big-O |
Notes |
| Add |
s.add(val) |
O(1) |
집합 요소 추가 |
| Containment |
x in/not in s |
O(1) |
포함 여부 확인 |
| Remove |
s.remove(val) |
O(1) |
요소 제거(없으면 에러) |
| Discard |
s.discard(val) |
O(1) |
요소 제거(없어도 에러x) |
| Pop |
s.pop() |
O(1) |
랜덤하게 하나 pop |
| Clear |
s.clear() |
O(1) |
|
| Construction |
set(…) |
O(len(…)) |
길이만큼 |
| check ==, != |
s != t |
O(len(s)) |
|
| <= or < |
s <= t |
O(len(s)) |
부분집합 여부 |
| 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)) |
여집합 |
| Iteration |
for v in s: |
O(N) |
전체 요소 순회 |
| Copy |
s.copy() |
O(N) |
|
dict 메소드 별 시간복잡도
| Operation |
Example |
Big-O |
Notes |
| Store |
d[k] = v |
O(1) |
집합 요소 추가 |
| Length |
len(d) |
O(1) |
|
| Delete |
del d[k] |
O(1) |
해당 key 제거 |
| get/setdefault |
d.get(k) |
O(1) |
key에 따른 value 확인 |
| Pop |
d.pop(k) |
O(1) |
pop |
| Pop item |
d.popitem() |
O(1) |
랜덤 데이터(key:value) pop |
| Clear |
d.clear() |
O(1) |
|
| View |
d.keys() |
O(1) |
key 전체 확인 |
| Values |
d.values() |
O(1) |
value 전체 확인 |
| Construction |
dict(…) |
O(len(…)) |
(key, value) tuple 갯수만큼 |
| Iteration |
for k in d: |
O(N) |
딕셔너리 전체 순회 |
Comments