algorithm - 大O还是大欧米茄？

Question

这是我对 A 是 O 还是 Ω 的 B ？你认为我答对了吗？

A               B           O   Ω
(log n)^3       N           No  Yes
2n^2+4n         4n^2        Yes No
n!              2^n         No  Yes
n^5             n^4         No  Yes
100             10000       Yes No
n^2             (1.5)^n     No  Yes

Answer 1

Big O 是渐近上界，而 Big Omega 是渐近下界。

• A = O(B) 当且仅当 limit A(n)/B(n) < C因为 n 接近无穷大，C 是一个正常数。
• A = Ω(B) 当且仅当 limit A(n)/B(n) > C > 0因为 n 接近无穷大，C 是一个正常数。

您可以使用 Wolframe Alpha找到这样的极限。

A               B           O   Ω
(log n)^3       N           Yes  No
2n^2+4n         4n^2        Yes Yes
n!              2^n         No  Yes
n^5             n^4         No  Yes
100             10000       Yes Yes
n^2             (1.5)^n     Yes  No

例如:

• limit n²/1.5ⁿ as n goes to infinite为 0。因此，我们知道 1.5ⁿ 比 n^2 增长得更快随着 n 越来越大。因此，1.5ⁿ 是 n² 的上限，但不是 n² 的下限。
• limit (2n^2+4n)/(4n^2) as n goes to infinite是 0.5。
  • 我们可以说 limit A(n)/B(n) < 1 .因此，A = O(B)。
  • 我们可以说 limit A(n)/B(n) > 0.4 > 0 .因此，A = Ω(B)。