以下函数的 Big O、Theta 和 Omega 有/解释？

Question

鉴于

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

可以做出哪些大的 Oh、Theta 和 Omega 语句？

我知道 big Oh 会是 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), "for big n"。

更困难的是计算 O/Theta/Omega 函数，例如：g(n) = 7 n^2 log(n^4).

===更新===

g(n)函数的主要问题是理解log(n^4)函数（在我看来它比简单的n难一点）。日志 (n^4) = 4*日志(n)。所以 O(log(n^4)) = Omega(log(n^4)) = Theta(log(n^4)) = log(n)，因为 log(n) <= log(n^4) < 4*日志（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

以下函数的 Big O、Theta 和 Omega 有/解释？

Big Oh, Theta, and Omega of the following function w/ explanation?

big-o

big-theta