两个复杂度O（（2n + 1）！）和O（n！）是否相等？ [英] Are the two complexities O((2n + 1)!) and O(n!) equal?

问题描述

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

解决方案

使用斯特林的逼近：

  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）。 / p>

This may be a naive question but I am new to the concept of Big-O notation and complexity and could not found any answer for this. I am dealing with a problem for which the algorithm (2n + 1)! times check a condition. Can I say that the complexity of the problem is O(n!) or the complexity is O((2n + 1)!)?

解决方案

Use Stirling's approximation:

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

Then

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

And now it's pretty clear why there's no hope of O((2n + 1)!) being O(n!): the exponential factors are way worse. It's more like O((2n + 1)!) is O((n!)^2).

这篇关于两个复杂度O（（2n + 1）！）和O（n！）是否相等？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！