개요
- 점근적 실행 시간(Asymptotic Running Time) 표기 시 가장 널리 쓰이는 수작헉 표기법 중 하나
- 언제 사용?
- 입력값이 커질 때
시간 복잡도와 공간 복잡도가 어떻게 증가하는지 분류하는 데 사용
- 알고리즘 효율성 분석에 활용
상한과 최악에 대한 개념 혼동 및 분할 상환 분석에 대한 정리
Big $O$
정의
- 입력값이 무한대로 향할 때
- 함수의 상한을 설명하는
- 수학적 표기 방법
점근적(Asymptotic) 실행 시간
개념
- 접근적 실행 시간
- = 시간 복잡도(Time Complexity)
- = 계산 복잡도(Computational Complexity): 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명
- 입력값이 무한대를 향할 때, 함수의 실행 시간의 추이 의미
- 왜 무한대를 향할 때가 의미 있을까?
- 입력값이 작으면 알고리즘이 복잡해도 컴퓨터 연산이 빨라 금방 끝난다
- 입력값이 크면 알고리즘의 효율성에 따라 수행 시간이 크게 차이날 수 있다
- 차이가 없으면 신경쓰지 않고, 차이가 나는 것에 신경을 쓰는 것
방법
4n^2 + 3n + 4 -> 4n^2 -> n^2 -> O(n^2)
종류
O(1): 해시 테이블의 조회/삽입
- 약속된 규칙에 따라 정해진 메모리 위치를 찾아가므로, 실행 시간이 항상 일정
- 대부분 가장 좋지만, 상수가 너무 크면 일정한 시간이 의미 없다
O($\log{n}$): 이진탐색
- 매우 큰 입력값에도 크게 영향을 받지 않는 편이다
- 로그 밑이 2거나 10이거나 차이가 있을까? 없다고 한다
- 간단하게, 밑 역시 고정된 값으로 보고 밑이 2가 됐든 10이 됐든 알고리즘의 시간 복잡도를 비교하는 데는 영향이 없다
O(n): 정렬되지 않은 리스트의 최소/최대값
- 선형 시간 알고리즘(Linear time algorithms)
- 말 그대로 일직선의 배열이 있으면 순차적으로 읽어 나가는 알고리즘
- 따라서 입력값만큼 실행 시간에 영향을 받는다
O($n \times \log{n}$): 병합정렬, Timmsort
- 분할한다는 점에서
O(log n)인 동시에 적어도 모든 수에 대해 한 번 이상은 비교하므로 n이 곱해진다
- 따라서 비교 기반의 정렬 알고리즘은 아무리 좋아도
O(n log n)보다 빠를 수 없다
- 단, 입력값이 최선인 경우
O(n)이 되는 Timsort 알고리즘도 있다
O($n^{2}$): 버블정렬
n번 반복문을 두 번 돌린다고 보면 이해하기 쉽다. $n^{3}$은 3중 반복문이 된다.- 같은 자료 구조의 선형 탐색을 여러번 하는 것은 당연히 비효율적이다
O($2^{n}$): 피보나치 재귀 계산
- 메모이제이션 같은 방법을 사용하지 않을 경우 같은 계산이 중첩적으로 이뤄진다
O(n!): 외판원 문제 brute force 풀이
- 최단 경로를 찾는
외판원 문제(TSP, Travelling Salesman Problem)을 brute force 방식으로 풀이하는 경우
공간 복잡도
- 빅오는 공간 복잡도를 표현한느 데에도 널리 쓰인다
- 알고리즘은 보통 시간과 공간이 트레이드 오프(Space-Time Tradeoff)되는 관계
- 실행 시간 빠름 -> 공간 많이 사용
- 공간 적게 사용 -> 실행 시간 느림
상한과 최악
상한
- $O$는 실행 시간의 상한을 의미
- $\Theta$는 실행 시간의 평균을 의미
- $\Omega$는 실행 시간의 하한을 의미
빅오 표기법과 최악
- $O$는 실행 시간의 상한을 적당히 정확하게 표현하는 방법일 뿐이다
- 즉, 표기법 != 최선/평균/최악의 케이스
- 최악의 경우가 있을 때, 상한은 아무리 늦게 실행되어도 그 안에는 된다는 것
- 가령 퀵 정렬이 ‘최선의 경우 n^100’라고 해도, 반드시 그 시간 안에 수행되므로 틀린 말은 아니지만, 의미가 없다
Amortized Analysis?
Amortization은 경제 용어로 감가/상각 중에서 상각이라고도 하며, 할부 상환이라고도 한다- 복잡도 계산 시, 알고리즘 전체가 아닌 최악의 경우만 살피는 경우 지나치게 비관적이라는 이유로 등장
- 대표적인 예로
동적 배열(dynamic array)
- 배열은 보통 시작 주소 값 + 인덱스 위치를 찾아가므로 아이템 삽입 시간은 O(1)이다
- 하지만 초기 배열에 할당된 메모리 공간이 부족해서
더블링되는 것을 보고 O(n) 시간 복잡도라고 하면 억울할 것이다
- 그래서 이
더블링과 같은 최악의 경우를 여러 번에 걸쳐 골고루 나눠주는 형태로 시간 복잡도를 계산
동적 배열
- 크기가 N인 배열에서 N+1번째 요소 삽입 시, 배열의 크기를 두 배로 늘리는 것
- 가령 아래와 같이 크기가 4인 배열이 있을 경우, 다섯번째 인덱스에 요소를 추가할 경우 더블링이 이뤄진다
동작: 삽입 삽입 삽입 삽입 삽입 <- 더블링
비용: 1 1 1 1 | 5
값: 10 21 12 63 | 34
| 단계 |
|
예제 |
| 1 |
n 개의 삽입 작업에 대해 n*Θ(1) = n |
4 |
| 2 |
기존 요소들을 이동 시키는 사이즈 더블링 작업에 Θ(n) |
4 |
| 3 |
총 n + 1 개의 요소 삽입 작업 |
5 |
| 4 |
((Θ(1) * n) + Θ(n)) / (n + 1) = Θ(1) |
(4 + 4) / 5 = 1.6 |
증명
n-th 요소 삽입 시 삽입 비용
A가 요소 삽입 후 공간이 남아 있다면 O(1)- 그렇지 않다면 O(n).
A 확장하는 데 소요되는 시간- 확장 시간은 최대 cn(c > 0)이라 가정
배열의 확장은 ${log_2{n}}$보다 클 수 없다
- 처음 사이즈가 2라고 한다면
\(\\2 \to 4 \\\)
\(4 \to 8 \\\)
\(8 \to 16 \\\)
\(\dots \\\)
\(2^{i} \to 2^{i+1} \\\)
- n이 입력된 후, 더블링이 되므로
A 배열의 크기는 최대 2n이 된다
\(\\ 2^{i+1} \le 2n \\\)
\({\log_2 2^{i+1}} \le {log_2 2n} \\\)
\({i} \le {log_2 n} \\\)
따라서 ${\log_2{n}}$보다 큰 배열 확장은 없다
n 개의 삽입에 대한 총 비용 한계
\[\sum\limits_{i=1}^n O(1) + \sum\limits_{i=1}^{\log_2 n} {c}\cdot{2^i} = O(n)\]
- 첫번째 파트(삽입)는 각 삽입에 대한 필수적인 상수 소요 시간
- 두번째 파트(복사)는 앞서 이미 확장에 소요했던 총 비용
- 따라서 첫번째 파트는 다음과 같이 계산되고
\(\\ O(1 + 1 + 1 + 1 + \dots) = O(n) \\\)
- 두번째 파트는 다음과 같이 계산된다
\(\\n = 2 \to {c}\cdot{2^{1}} \\\)
\(n = 3 \to {c}\cdot{2^{1}} \\\)
\(n = 4 \to {c}\cdot{2^{1}} + {c}\cdot{2^{2}} \\\)
\(n = 5 \to {c}\cdot{2^{1}} + {c}\cdot{2^{2}} \\\)
\(n = 6 \to {c}\cdot{2^{1}} + {c}\cdot{2^{2}} \\\)
\(n = 7 \to {c}\cdot{2^{1}} + {c}\cdot{2^{2}} \\\)
\(n = 8 \to {c}\cdot{2^{1}} + {c}\cdot{2^{2}} + {c}\cdot{2^{3}} \\\)
\(\dots \\\)
\(O(1 + 1\cdot2^{1} + 1\cdot2^{2} + 1\cdot2^{log_2n} - 1)\)
\(\\ = O(\frac{1 - 2^{log_2n + 1}}{1 - 2} - 1) \\\)
\(= O(2\cdot2^{log_2n})\\\)
- 첫번째 파트와 두번째 파트를 합하면
\(= O(n + 2\cdot2^{log_2n}) \\\)
\(= O(n) \\\)
참고