algorithm - 我们如何扩展（logn）！和（登录！）！确定复杂性？

Question

我知道日志n！给出了 O(nlogn) 的复杂度，但如何扩展上述内容？第二个可以简化为 (nlogn)!。请澄清这一点。

score 3 · Accepted Answer

(log(n))!您可以估计将身份 $x^log(y)=y^log(x)$ 与产品估计一起使用的上限和下限。

对于上限：

$上限$

对于下限：

$下限$

结合起来你会得到：

$结合$

所以至少：

$O(n^{log(log(n))})$

显然，由于产品的非整数索引边界，（in）方程在某种程度上是“奇怪的”。

更新：hwlau使用英镑近似值给出的界限较低 (by sqrt(log(n))/n) 并且应该很紧。

$更严格的界限$

score 2 · Accepted Answer

更新：不，您不能(N ln N)!在第二个公式中使用。下面使用第一种情况解释原因。

ln(z!) = (z+1/2) ln z - z + O(1)...

请注意，z这里保留了额外的内容，原因很快就会很明显。x = log N现在，如果我们让

(ln N)! = x! = exp(ln x!)
~ exp((x+1/2) ln x - x) = x^(x+1/2) exp(-x)
= (ln N)^((ln N)+1/2) / N

我们保留的额外项是的倒数N，它肯定会对复杂性产生影响，因为我们不能简单地丢弃某些东西的 exp。如果我们表示g(N)上面的近似值和f(N) = (ln N)!，那么lim f(N)/g(N) = sqrt(2 pi) < inf，那么f = O(g)

对于(ln N!)!，有点复杂，我用mathematica检查极限，它提示展开

ln(z!) ~ (z+1/2) ln z - z + ln(sqrt(2pi))

足够的。我没有关于什么时候可以停止的一般规则。通常，可能无法仅使用有限项。但在这种情况下，我们可以。

如果您只需要一个松散的界限，对于第一个公式，您实际上可以丢弃该-z术语，因为(z+1/2) ln z > (z+1/2) ln z - z.

2 回答 2