다음 함수의 큰 오, 세타 및 오메가 설명이 있습니까?

Question

는

f(n) = 2 n^3 + 7 n^2 log(n^4) 

을 감안할 때 할 수있는 큰 아, 세타, 오메가 문은 무엇입니까?

큰 오는 이 될 것이라고 알고 있지만, 다른 것들을 위해 무엇을 찾아야할지 모르겠습니다. 나는 그것이 n^3에 묶여 있고, 더 좋을 수 없다는 것을 알 수 있습니다.

Answer 1

큰 O 표기에 관해서는 wiki에서 설명한대로.

빅 O :

O(f(n)) = n^3, because f(n) = 2n^3 + (7n^2)*log(n^4) =< 2n^3 + (7n^2)*n =< 9n^3, 
for big enough n. As explained below log(n^4) <= n, for big enough n. 

큰 오메가 :

Omega(f(n)) = n^3; because f(n) = 2n^3 + (7n^2)*log(n^4) >= 2n^3 >= n^3, 
for big enough n. 
You can assume that `(7n^2)*log(n^4) > 0` so 2n^3 + (7n^2)*log(n^4) > 2n^3 >= n^3. 

큰 세타 예를 n^3이 7 n^2 log(n^4)을 지배 당신에

Theta(f(n)) = n^3; because it O(f(n)) = Omega(f(n)) = n^3, 

, "큰 N에 대한".

g(n) = 7 n^2 log(n^4)과 같은 함수에 대해 O/Theta/Omega를 계산하는 것이 더 어려울 것입니다.

=== 업데이트 ===은g(n) 기능을 가진 가장 큰 문제는 log(n^4) 기능을 이해하는 것입니다

(제 생각에 그것은 n 간단한보다 약간 어렵습니다). log (n^4) = 4 * log (n). log (n) log (n) < = log (n^4)이므로 0 (log (n^4)) = 오메가 < 4 * log (n). 이것은 log (n^4) < = n을 의미합니다. n은 충분히 큰 값입니다.

마지막이 우리를 인도 :

(7 n^2)*log(n^4) = (7n^2)*4log(n) = 28*(n^2)*(log n) 
1*(n^2)*(log n) <= 28*(n^2)*(log n) <= 29*(n^2)*(log n) 
// O(g(n))= n^2 * log n 
// Omega(g(n))= n^2 * log n 
// Theta(g(n))= n^2 * log n