大O还是大欧米茄？

Big O or Big Omega?

这是我对 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

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。因此，随着n越来越大，我们知道1.5ⁿ比n^2增长得更快。因此，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).