哪个更快？ O(2^n) 或 O(n!)

Question

我正在研究算法的复杂性，我试图弄清楚这个在我脑海中运行的问题 - O(n!) 比 O(2^n) 快还是相反？

Answer 1

O(2^n) 是 2 * 2 * 2 * ... 其中 O(n!) 是 1 * 2 * 3 * 4 * ...

O(n!) 会很快变大 - 所以 O(2^n) 更快。

例如：2^10 = 1024 和 10! = 3628800

Answer 2

您可以尝试使用 斯特林近似值 来计算 n! https://en.wikipedia.org/wiki/Stirling%27s_approximation

 n! = (n / e)^n * sqrt(2 * Pi * n) * (1 + o(n))

现在，让我们比较一下

 O(n!) <=> O(2^n)

为了找出正确的字母 <、= 或 > 让我们计算 limit

 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^)

哪个更快？ O(2^n) 或 O(n!)

Which one is faster? O(2^n) or O(n!)

math

time-complexity