같은 방정식이 다른 big-O 값을주는 이유

Question

강의 슬라이드에 제시된 예에서 big-o 분석은 나를 혼란스럽게합니다.

그것은 상태 : 2N^2 + 4N = O (N^2) 2N^2 + 4N = O는 (N^4)

사람이 동일한 방정식 다른 결과를 생성하는 방법을 설명 할 수 있을까? 감사합니다

Answer 1

우선 "="은 "그와 같음"을 의미하지 않으며, 알고리즘 분석의 의미에서 "있는"것을 의미합니다. 큰-O의 요점은이를 만족하는 것입니다

f(x)는 c가 양수가 O(g(x))0<=|f(x)|<=c*g(x) IFF에 곳입니다.

따라서 귀하의 경우 2n^2 + 4n = O(n^2) AND 2n^2 + 4n = O(n^4)이 true입니다. 그러나 알고리즘을 설명 할 때는 항상 "최상의 함수"를 사용하므로 O(n^2)을 사용합니다.

f(x)은 Ω(h(x)) 인 경우 0<=c*h(x)<=|f(x)|입니다. 당신이 h(x)=g(x)이있는 경우 지금, 그 f(x)는 Θ(g(x))