Большая О или Большая Омега?

Question

Вот мои ответы Является ли A или Ω 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 as n приближается к бесконечности, а C - положительная постоянная.
• A = Ω (B) тогда и только тогда, когда limit A(n)/B(n) > C > 0, поскольку n приближается к бесконечности, а C - положительная постоянная.

Wolframe Alpha Чтобы найти такой предел, вы можете использовать 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 при п становится все больше и больше. Таким образом, 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).