Что такое O (log (n!)) И O (n!) И приближение Стирлинга
Что такое O(log(n!)) и O(n!)? Я считаю, что это O(n log(n)) и O(n^n)? Зачем?
Я думаю, что это связано с аппроксимацией Стирлинга, но я не очень хорошо объясняю это.
Может ли кто-то исправить меня, если я ошибаюсь (около O(log(n!)= O(n log(n)))? И если возможно, математика в более простых выражениях? Я не думаю, что мне нужно будет доказать, что на самом деле я просто хочу понять, как это работает.
Ответы
Ответ 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)), они эквивалентны классам большой-Oh.
Ответ 2
По приближению Стирлинга,
log(n!) = n log(n) - n + O(log(n))
Для больших n в правой части доминирует член n log (n). Это означает, что O (log (n!)) = O (n log (n)).
Более формально, одно определение "большого 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).
