以下功能的大哦，theta和歐米茄w /說明？

Question

鑑於

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

什麼是可以進行大哦，西塔，和歐米茄報表？

我明白大哦會是O(n^3)，但我不確定要找什麼，其他人。 我看到的全部都是受n^3的約束，不可能更好。

Answer 1

如在wiki關於大O表示法的文章中所述。

大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. 

大西塔：

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

在您例如n^3主導7 n^2 log(n^4) 「爲大N」。

更難以計算O/Theta/Omega的功能，如：g(n) = 7 n^2 log(n^4)。

=== UPDATE ===

與g(n)功能的主要問題是瞭解log(n^4)功能（在我看來，它比簡單的n更難一點）。 log（n^4）= 4 * log（n）。 （log（n^4））= Omega（log（n^4））= Theta（log（n^4））= log（n），因爲log（n）< = log < 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