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

Question

这可能是一个天真的问题,但我对Big-O符号和复杂性的概念不熟悉,也找不到任何答案.我正在处理一个算法(2n + 1)的问题!时间检查一个条件.我能说问题的复杂性是O(n!)还是复杂度是O((2n + 1)!)？

Answer 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).