For a better world

시간 복잡도

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

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

표기법 간의 관계

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$

정렬 알고리즘 비교

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/