반응형
시간 복잡도
| Big-Ω(빅-오메가) | 최선일 때 (best case)의 연산 횟수를 나타낸 표기법 |
| Big-θ(빅-세타) | 보통일 때 (average case)의 연산 횟수를 나타낸 표기법 |
| Big-O(빅-오) | 최악일 때 (worst case)의 연산 횟수를 나타낸 표기법 |
- 위 세 가지 표기법은 시간 복잡도를 각각 최선, 중간(평균), 최악의 경우에 대하여 나타내는 방법이다.
가장 자주 사용되는 표기법❗️ Big-O 표기법
- 빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문이다.
- “최소한 특정 시간 이상이 걸린다” 혹은 “이 정도 시간이 걸린다”를 고려하는 것보다 “이 정도 시간까지 걸릴 수 있다”를 고려해야 그에 맞는 대응이 가능하다.
시간복잡도에서 중요하게 보는것은 가장큰 영향을 미치는 n의 단위이다.
1 O(1) --> 상수
2n + 20 O(n) --> n이 가장 큰영향을 미친다.
3n^2 O(n^2) --> n^2이 가장 큰영향을 미친다.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 제곱.
시간 복잡도 최선의 경우를 고려한 경우
- 결과를 반환하는 데 최선의 경우 1초, 평균적으로 1분, 최악의 경우 1시간이 걸리는 알고리즘을 구현했고, 최선의 경우를 고려한다고 가정하겠다.
- 이 알고리즘을 100번 실행한다면, 최선의 경우 100초가 걸린다.
- 만약 실제로 걸린 시간이 1시간을 훌쩍 넘겼다면, ‘어디에서 문제가 발생한 거지?’란 의문이 생긴다.
- 최선의 경우만 고려하였으니, 어디에서 문제가 발생했는지 알아내기 위해서는 로직의 많은 부분을 파악해야 하므로 문제를 파악하는 데 많은 시간이 필요하다.
시간 복잡도 중간의 경우를 고려한 경우
- 평균값을 기대하는 시간 복잡도를 고려한다면 어떨까?
- 알고리즘을 100번 실행할 때 100분의 시간이 소요된다고 생각했는데, 최악의 경우가 몇 개 발생하여 300분이 넘게 걸렸다면 최선의 경우를 고려한 것과 같은 고민을 하게 된다.
시간 복잡도 최악의 경우를 고려한 경우
- 극단적인 예이지만, 위와 같이 최악의 경우가 발생하지 않기를 바라며 시간을 계산하는 것보다는 ‘최악의 경우도 고려하여 대비’하는 것이 바람직하다.
- 따라서 다른 표기법보다 Big-O 표기법을 많이 사용한다.
- Big-O 표기법은 ‘입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?’를 표기하는 방법이다.
O(1) : 상수
아래 예제 처럼 입력에 관계없이 복잡도는 동일하게 유지된다.
def hello_world():
print("hello, world!")
O(N) : 선형
입력이 증가하면 처리 시간또는 메모리 사용이 선형적으로 증가한다.
def print_each(li):
for item in li:
print(item)
O(N^2) : Square
반복문이 두번 있는 케이스
def print_each_n_times(li):
for n in li:
for m in li:
print(n,m)
O(log n) O(n log n)
주로 입력 크기에 따라 처리 시간이 증가하는 정렬알고리즘에서 많이 사용된다.
다음은 이진검색의 예이다.
def binary_search(li, item, first=0, last=None):
if not last:
last = len(li)
midpoint = (last - first) / 2 + first
if li[midpoint] == item:
return midpoint
elif li[midpoint] > item:
return binary_search(li, item, first, midpoint)
else:
return binary_search(li, item, midpoint, last)
시간복잡도를 구하는 요령
각 문제의 시간복잡도 유형을 빨리 파악할 수 있도록 아래 예를 통해 빠르게 알아 볼수 있다.
- 하나의 루프를 사용하여 단일 요소 집합을 반복 하는 경우 : O (n)
- 컬렉션의 절반 이상 을 반복 하는 경우 : O (n / 2) -> O (n)
- 두 개의 다른 루프를 사용하여 두 개의 개별 콜렉션을 반복 할 경우 : O (n + m) -> O (n)
- 두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우 : O (n²)
- 두 개의 중첩 루프를 사용하여 두 개의 다른 콜렉션을 반복 할 경우 : O (n * m) -> O (n²)
- 컬렉션 정렬을 사용하는 경우 : O(n*log(n))
공간 복잡도
공간 복잡도도 시간 복잡도와 유사하게 빅오 표기법을 사용합니다.
다음 알고리즘을 보고 공간 복잡도를 계산해 보겠습니다.
int sum(int a[], int n)
{
int x = 0;
for(int i = 0; i < n; i++) {
x = x + a[i];
}
return(x);
}위 알고리즘은 4개의 변수를 사용하고 있습니다.
- int arr[n] : 4*n byte (입력 공간)
- int n : 4 byte (입력 공간)
- int x : 4 byte (보조 공간)
- int i : 4 byte (보조 공간)
총 4n+12 에 메모리를 요구합니다. 메모리가 입력 값에 따라 선형적으로 증가하기 때문에 공간 복잡도는 O(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) |