algorithm - 两个复杂度 O((2n + 1)!) 和 O(n!) 是否相等？

这可能是一个幼稚的问题，但我对 Big-O 表示法和复杂性的概念很陌生，因此找不到任何答案。我正在处理算法(2n + 1)的问题!次检查条件。我可以说问题的复杂度是 O(n!) 还是复杂度是 O((2n + 1)!)？

最佳答案

使用 Stirling's approximation :

n! ~ (n / e)^n * sqrt(2 * pi * n)

然后

(2n + 1)! ~ ((2n + 1) / e)^(2n + 1) * sqrt(2 * pi * (2n + 1))
          >= (2n / e)^(2n) * sqrt(2 * pi * 2n)
          = 2^2n * (n / e)^(2n) * sqrt(2) * sqrt(2 * pi * n)
          = sqrt(2) * (2^n)^2 * ((n / e)^n)^2 * sqrt(2 * pi * n)

现在很清楚为什么 O((2n + 1)!) 没有希望成为 O(n!) :指数因素更糟。更像是 O((2n + 1)!) 是 O((n!)^2) 。

关于algorithm - 两个复杂度 O((2n + 1)!) 和 O(n!) 是否相等？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/18044808/