두개의 함수 f(n)과 g(n)이 주어졌을 때, 모든 n >= k에 대하여 f(n) <= Cg(n)을 만족하는 두개의 상수 c와 k가 존재하면 f(n)의 빅오는
O(g(n))이다.
해당 정리에 쫄필요없다.
간단한 정의였다.
예를들어
n^2 + 100과 3n^2이 있다고 생각하자.
n=1
n^2 + 100 = 101
3n^2 = 3
n=2
n^2 + 100 = 104
3n^2 = 12
위의 결과를 보면 결과에 가장 큰 영향을 끼치는 것은 n^2이냐 3n^2냐가 아니라 n^2+100의 100이 가장 영향을 끼치는 것으로 보인다.
하지만 이는 틀리다.
낮은 값을 계산할 경우에는 100이 커보이지만 값이 커질 수록 100의 존재는 아예 없어진다.
n = 64
n^2 + 100 = 4096 + 100
3n^3 = 4096 * 3
이처럼 100은 아무 의미가 없다. 의미 있는 것은 n^2이다.
즉 f(n) = n^2, Cg(n) = 3n^2
즉 빅오는 n^2이다.
