这可能是一个幼稚的问题，但我对 Big-O 表示法和复杂性的概念并不陌生，因此找不到任何答案。我正在处理算法（2n + 1）的问题！次检查一个条件。我可以说问题的复杂度是 O(n!) 还是复杂度是 O((2n + 1)!)？
问问题
797 次
4 回答
6
使用斯特林近似：
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)。
于 2013-08-04T16:29:45.450 回答
3
令 (N,c) 是任何有序的正常数对。令 n 为满足 n>N 且 n>c 的任意整数。
那么（2n+1）！> (2n+1)*n! > cn！
因此对于任何一对正常数 (N,c) 都存在 n>N 使得 (2n+1)! > cn!，所以 (2n+1)！不是 O(n!)。
O((2n+1)!) 包含一个函数，(2n+1)!，它不在 O(n!) 中，所以 O((2n+1)!) 和 O(n!) 不一样.
（我同意想要 LaTeX。）
于 2013-08-04T17:50:53.557 回答
2
这是定义：https ://en.wikipedia.org/wiki/Big_O_notation 。所以我们需要检查是否存在一个常数 c 和 n0 使得：
(2n+1)! < cn! for n > n0
直观地，从观察如何（2n+1）！和n！表现：
http://www.wolframalpha.com/input/?i=n!+%3E%282n+%2B1%29！
(2n+1)！只是快了两倍，所以不管“c”如何，它总是会达到 n!。所以你不能简化为 n!。
于 2013-08-04T16:09:00.950 回答
0
(2n+1)！= n!(n+1)...(2n+1)
O((2n+1)!) = O(n!)O((n+1)...(2n+1))
==>
O(1) = o((n+1)...(2n+1))
O(n!) = o((2n+1)!)
于 2013-08-04T16:56:46.727 回答