시간 복잡도 정리

시간 복잡도

시간 복잡도란 알고리즘의 효율성을 판단하기 위한 지표로서, 알고리즘의 절대시간이 아닌,  알고리즘을 수행하는데 사용되는 연산들이 몇 번 이루어지는가에 대한 것을 수로 표기한 것이다. 연산에는 산술, 대입, 비교, 이동이 있다. 시간 복잡도, 즉 성능 측정에 사용되는 표기법은 크게 세 가지로 나뉘며 Big-O, Big-Omega($\Omega$), Theta($\theta$)가 있다.

• Big-O

모든 $n$, $n \gt n_0$에 대해 $f(n) \le c\times g(n)$인 조건을 만족시키는 두 양의 상수 $c$와 $n_0$가 존재하기만 하면 $f(n)=O(g(n))$이다.

예를 들면 $O(n)$: 최악의 경우 $n$번까지 수행되면 프로그램을 끝낼 수 있다.

• Big-Omega

모든 $n$, $n \gt n_0$에 대해 $f(n) \gt c\times g(n)$인 조건을 만족시키는 두 양의 상수 $c$와 $n_0$가 존재하기만 하면 $f(n)=\Omega(g(n))$이다.

예를 들면 $O(n)$: 최소 $n$번은 수행되어야 프로그램을 끝낼 수 있다.

• Theta

모든 $n$, $n \gt n_0$에 대해 $c_1\times g(n) \le f(n) \le c_2\times g(n)$인 조건을 만족시키는 세 양의 상수 $c_1, c_2, n_0$가 존재하기만 하면 $f(n)=\theta(g(n))$이다.

$\Omega와\ O$의 교집합, 즉 차수가 같은 문제이다.

추가적으로 Small-O, Small-omega($\omega$) 표기법도 존재한다.

Small-O는 Big-O에서 등호를 뺀다.

예를 들면 $O(n)$: 최악의 경우에도 n번 미만으로 수행되면 프로그램은 끝낼 수 있다.

Small-O와 Big-O의 차이점은 다음과 같다.

- Big-O는 실수 $c>0$ 중에서 하나만 성립해도 된다.

- Small-O는 모든 실수 $c>0$에 대해서 성립해야 한다.

---

Big-O 표기법 성능 비교

시간 복잡도 함수의 그래프

Better $O(1)$ < $O(log\ n)$ < $O(n)$ < $O(n\times log\ n)$ < $O(n^2)$ < $O(2^n)$ < $O(n!)$ Worse

상수 함수 < 로그 함수 < 선형 함수 < 다항 함수 < 지수 함수 < 재귀 함수

---

Big-O 표기법 예제

• $O(1)$: Operation push and pop on Stack
• $O(log\ n)$: Binary Tree
• $O(n)$: for loop
• $O(n\times log\ n)$: Quick Sort, Merge Sort, Heap Sort
• $O(n^2)$: Double for loop, Insert Sort, Bubble Sort, Selection Sort
• $O(2^n)$: Fibonacci Sequence

---

시간 복잡도 분석 종류

$T(n)$: Every-case anlaysis

• 입력크기(input size)에만 종속
• 입력값과는 무관하게 결과값은 항상 일정

$W(n)$: Worst-case analysis

• 입력크기와 입력값 모두에 종속
• 단위연산이 수행되는 횟수가 최대인 경우 선택

$A(n)$: Average-case analysis

• 입력크기와 입력값 모두에 종속
• 모든 입력에 대해 단위연산이 수행되는 기대치(평균)
• 각 입력에 대해서 확률 할당 가능

$B(n)$: Best-case analysis

• 입력크기와 입력값 모두에 종속
• 단위연산이 수행되는 횟수가 최소인 경우 선택

---

표기법 간의 관계

표기법	의미
$f = \omega(g)$	$f$는 $g$보다 크다, $f \gt g$
$f = \Omega(g)$	$f$는 $g$보다 크거나 같다, $f \ge g$
$f = \theta(g)$	$f$는 $g$와 대략 같다, $f = g$
$f = O(g)$	$f$는 $g$보다 작거나 같다, $f \le g$
$f = o(g)$	$f$는 $g$보다 작다, $f \lt g$

---

Big-O 계산 실습

a=10 # Constant 1
b=20 # Constant 1
c=30 # Constant 1

for i in range(n):
 for j in range(n):
    x = i * i # n^2
    y = j * j # n^2
    z = i * j # n^2

for k in range(n):
    w = a * k + 40 # n
    v = b * b # n

$T(n) =  3n^2 + 2n + 3$

$T(n) = On^2$

---

정렬 알고리즘 비교

Sorting Algorithm	공간 복잡도		시간 복잡도
	최악	최선	평균	최악
Bubble Sort	$O(1)$	$O(n)$	$O(n^2)$	$O(n^2)$
Heap Sort	$O(1)$	$O(n\times log\ n)$	$O(n\times log\ n)$	$O(n\times log\ n)$
Insertion Sort	$O(1)$	$O(n)$	$O(n^2)$	$O(n^2)$
Merge Sort	$O(1)$	$O(n\times log\ n)$	$O(n\times log\ n)$	$O(n\times log\ n)$
Quick Sort	$O(log \ n)$	$O(n\times log\ n)$	$O(n\times log\ n)$	$O(n^2)$
Selection Sort	$O(1)$	$O(n^2)$	$O(n^2)$	$O(n^2)$
Shell Sort	$O(1)$	$O(n)$
Smooth Sort	$O(1)$	$O(n)$	$O(n\times log\ n)$	$O(n\times log\ n)$

---

Reference

[1] https://arer.tistory.com/99

[2] https://noahlogs.tistory.com/27

[3] https://sehoi.github.io/2014-03-03/time-complexity/

[4] https://ratsgo.github.io/data%20structure&algorithm/2017/09/13/asymptotic/

[5] https://blog.chulgil.me/algorithm/

[6] https://wayhome25.github.io/cs/2017/04/20/cs-26-bigO/