We can predict how an algorithm will perform for large input sets, based on its performance for moderate input sets.
Big-Θ
Θ(g(n)) = { f(n): there exist positive c1, c2, and n0 such that 0 <= c1*g(n) <= f(n) <= c2*g(n) for all n >= n0 }.
- 집합이므로 f(n)이 Θ(g(n))에 포함된다고 표기할 수 있다. 다만 표기상 f(n) = Θ(g(n))이라고 한다.
- Θ(g(n))에 속하는 모든 함수 f(n)은
충분히 큰 n에 대해 0 이상이어야 한다.
- 왜냐, 어차피 성장률 비교이기 때문에.
- 만약 음수가 된다면, Θ(g(n))은 공집합이 된다.
Big-O
Θ에서 하한이 없어진 버전.
O(g(n)) = {f(n) : there exist positive constants c, n0 such that 0 <= f(n) <= c*g(n) for all n >= n0}.
Big-Ω
Θ에서 상한이 없어진 버전.
Ω(g(n)) = {f(n) : there exist positive constants c, n0 such that c*g(n) <= f(n) for all n >= n0}.Properties
- if T1(n) = O(f(n)) && T2(n) = O(g(N)),
- T1(n) + T2(n) = max(O(f(n)), O(g(n))
- T1(n) * T2(n) = O(f(n) * g(n))
- O(c * f(n)) = O(f(n))
Names
- O(n^3) : Cubic
- O(n^2) : Quadratic
- O(nlogn)
- O(n) : Linear
Theorem 3.1
For any two functions f(n) and g(n), we have f(n) = Θ(g(n)) iff f(n) = O(g(n)) and f(n) = Ω(g(n)).
-> 즉, 하한과 상한의 함수가 같아야 세타가 존재한다.
Growth compare
log(n) < n < nlog(n) < n^2 < 2^n
