Какая функция растет быстрее, экспоненциально (например, 2 ^ n, n ^ n, e ^ n и т.д.) или factorial (n!)? Ps: Я просто где-то читал, n! растет быстрее, чем 2 ^ п.
Какая функция растет быстрее, экспоненциально или факториально?
Ответ 1
п! в конечном счете растет быстрее экспоненты с постоянной базой (2 ^ n и e ^ n), но n ^ n растет быстрее, чем n! так как основание растет с ростом n.
Ответ 2
n! = n * (n-1) * (n-2) * ...
n^n = n * n * n * ...
Каждый член после первого в n^n больше, поэтому n ^ n будет расти быстрее.
Ответ 3
n^n становится больше, чем n! - превосходное объяснение см. в ответе @AlexQueue.
В остальных случаях читайте дальше:
Факторные функции асимптотически растут больше экспоненциальных функций, но не сразу понятно, когда начинается различие. Например, для n=5 и k=10 факториал 5!=120 все еще меньше, чем 10^5=10000. Чтобы определить, когда факторные функции начинают расти, нам нужно сделать небольшой математический анализ.
Мы используем формулу Стирлинга и основные логарифмические манипуляции:
log_k(n!) ~ n*log_k(n) - n*log_k(e)
k^n = n!
log_k(k^n) = log_k(n!)
n*log_k(k) = log_k(n!)
n = log_k(n!)
n ~ n*log_k(n) - n*log_k(e)
1 ~ log_k(n) - log_k(e)
log_k(n) - log_k(e) - 1 ~ 0
log_k(n) - log_k(e) - log_k(k) ~ 0
log_k(n/(e*k)) ~ 0
n/(e*k) ~ 1
n ~ e*k
Таким образом, как только n достигает почти в 3 раза размера k, факторные функции начнут расти больше, чем экспоненциальные функции. Для большинства реальных сценариев мы будем использовать большие значения n и малые значения k, поэтому на практике мы можем предположить, что факторные функции строго больше, чем экспоненциальные функции.