#math #time-complexity
Вопрос:
Я изучаю сложность алгоритма и пытаюсь ответить на один вопрос, который возникает у меня в голове: O (n!) быстрее, чем O (2 ^ n) или наоборот?
Ответ №1:
O(2^n) 2 * 2 * 2 * ... где O(n!) 1 * 2 * 3 * 4 * ...
O(n!) будет быстро расти намного больше — так O(2^n) быстрее.
Например: 2^10 = 1024 и 10! = 3628800
Комментарии:
1. да, но если мы возьмем, например, n = 3, то O (2 ^ n) равно 8, тогда как O (n!) равно 6, что означает, что при небольшом значении n O (2 ^ n) быстрее, чем O (n!).. вот что меня здесь смущает
2. @Integrity Обозначение Big-O означает .. когда N приближается к бесконечности. так что это не имеет значения при малых значениях N, важно, что происходит, когда N становится большим.
Ответ №2:
Вы можете попробовать поработать с приближением Стирлинга для n!
https://en.wikipedia.org/wiki/Stirling’s_approximation
n! = (n / e)^n * sqrt(2 * Pi * n) * (1 o(n))
Теперь давайте сравним
O(n!) <=> O(2^n)
Для того, чтобы узнать правильную букву < , = или > давайте вычислим предел
lim (n! / 2^n) =
n -> inf
lim (n / e)^n * sqrt(2 * pi * n) / 2^n >=
n -> inf
lim n^n / (2 * e)^n >= // when n > 4 * e
n -> inf
lim (4 * e)^n / (2 * e)^n =
n -> inf
lim 2^n = inf
n -> inf
Итак
lim (n! / 2^n) = inf
n -> inf
это означает, что O(n!) > O(2^)