시간 복잡도란 알고리즘의 효율성을 판단하기 위한 지표로서, 알고리즘의 절대시간이 아닌, 알고리즘을 수행하는데 사용되는 연산들이 몇 번 이루어지는가에 대한 것을 수로 표기한 것이다. 연산에는 산술, 대입, 비교, 이동이 있다. 시간 복잡도, 즉 성능 측정에 사용되는 표기법은 크게 세 가지로 나뉘며 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번 미만으로 수행되면 프로그램은 끝낼 수 있다.
$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 1for i in range(n):
for j in range(n):
x = i * i # n^2
y = j * j # n^2
z = i * j # n^2for k in range(n):
w = a * k + 40# n
v = b * b # n
