알고리즘 분석 ( 시간복잡도 )

1. big-oh(상향), big-omega(하향), big-theta(평균) 표기법 정의

* big-oh

 두 개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n >= n0 에 대하여 |f(n)| <= c |g(n)|을 만족하는 2개의 상수 c와 n0가 존재하면 f(n) = O(g(n))이다.

* big-omega

 두 개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n >= n0 에 대하여 |f(n)| >= c |g(n)|을 만족하는 2개의 상수 c와 n0가 존재하면 f(n) = 오메가(g(n))이다.

*big-theta

 두 개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n >= n0 에 대하여 c1|g(n)| <= f(n) <= c2|g(n)| 을 만족하는 3개의 상수 c1, c2와 n0가 존재하면 f(n) = 세타(g(n))이다.

- big-theta가 가장 이상적으로 보이지만, 모든 입력을 고려하여 각 입력이 발생하는 확률을 구하기는 어려움.

- 최악의 경우(big-oh)가 실행 시간의 알고리즘의 시간 복잡도 척도로 가장 많이 쓰임.

2. n이 증가할 때 시간 복잡도 함수의 증가

시간 복잡도	n
	1	2	4	8	16	32
	1	1	1	1	1	1
	0	1	2	3	4	5
	1	2	4	8	16	32
	0	2	8	24	64	160
	1	4	16	64	256	1024
	1	8	64	512	4096	32768
	2	4	16	256	65536	4294967296
	1	2	24	40326	20922789888000	26313*10^33