Что такое O (log (n!)) И O (n!) И приближение Стирлинга

Question

Что такое O(log(n!)) и O(n!)? Я полагаю, что это O(n log(n)) и O(n^n)? Зачем?

Я думаю, что это связано с приближением Стирлинга, но я не очень хорошо понимаю объяснение.

Может ли кто-нибудь поправить меня, если я ошибаюсь (о O(log(n!) = O(n log(n)))? И если возможно, математика в более простых сроках? Не думаю, что мне нужно будет доказывать, что на самом деле я просто хочу понять, как это работает.

Answer 1

O(n!) не эквивалентно O(n^n). Это асимптотически меньше O(n^n).

O(log(n!)) равно O(n log(n)). Вот один из способов доказать это:

Обратите внимание, что с помощью правила ведения журнала log(mn) = log(m) + log(n) мы можем видеть, что:

log(n!) = log(n*(n-1)*...2*1) = log(n) + log(n-1) + ... log(2) + log(1)

Доказательство того, что O(log(n!)) ⊆ O(n log(n)):

log(n!) = log(n) + log(n-1) + ... log(2) + log(1)

Что меньше чем:

log(n) + log(n) + log(n) + log(n) + ... + log(n) = n*log(n)

Итак, O(log(n!)) является подмножеством O(n log(n))

Доказательство этого O(n log(n)) ⊆ O(log(n!)):

log(n!) = log(n) + log(n-1) + ... log(2) + log(1)

Что больше чем (левая половина этого выражения со всеми (n-x), замененными на n/2:

log(n/2) + log(n/2) + ... + log(n/2) = floor(n/2)*log(floor(n/2)) ∈ O(n log(n))

Итак, O(n log(n)) является подмножеством O(log(n!)).

Начиная с O(n log(n)) ⊆ O(log(n!)) ⊆ O(n log(n)), они являются эквивалентными классами большого класса.

Answer 2

По приближению Стерлинга,

log(n!) = n log(n) - n + O(log(n))

Для больших n в правой части преобладает член n log (n). Это означает, что O (log (n!)) = O (n log (n)).

Более формально, одно определение "Big O" состоит в том, что f (x) = O (g (x)) тогда и только тогда, когда

lim sup|f(x)/g(x)| < ∞ as x → ∞

Используя приближение Стирлинга, легко показать, что log (n!) ∈ O (n log (n)), используя это определение.

Аналогичный аргумент применим к n !. Взяв экспоненту обеих сторон приближения Стирлинга, мы находим, что для больших n, n! ведет себя асимптотически как n ^ (n + 1) / exp (n). Поскольку n / exp (n) → 0 при n → ∞, мы можем заключить, что n! ∈ O (n ^ n), но O (n!) Не эквивалентно O (n ^ n). В O (n ^ n) есть функции, которых нет в O (n!) (Например, само n ^ n).