什么是O(log(n!))和O(n!)和斯特林近似

Question

什么是O(log(n!))和O(n!)？我相信它是O(n log(n))和O(n^n)？为什么？

我认为这与斯特林近似有关,但我没有得到很好的解释.

如果我错了(关于O(log(n!)= O(n log(n))),有人可以纠正我吗？如果可能,数学用简单的术语表示？我认为我不需要证明实际上我只是想知道它是如何工作的.

Answer 1

O(n!)不等于O(n^n).它渐近地小于O(n^n).

O(log(n!))等于O(n log(n)).以下是证明这一点的一种方法:

请注意,通过使用日志规则,log(mn) = log(m) + log(n)我们可以看到:

log(n!) = log(n*(n-1)*...2*1) = log(n) + log(n-1) + ... log(2) + log(1)

证明O(log(n!)) ? O(n log(n)):

log(n!) = log(n) + log(n-1) + ... log(2) + log(1)

哪个小于:

log(n) + log(n) + log(n) + log(n) + ... + log(n) = n*log(n)

所以O(log(n!))是一个子集O(n log(n))

证明O(n log(n)) ? O(log(n!)):

log(n!) = log(n) + log(n-1) + ... log(2) + log(1)

哪个大于(表达式的左半部分全部(n-x)替换为n/2:

log(n/2) + log(n/2) + ... + log(n/2) = floor(n/2)*log(floor(n/2)) ? O(n log(n))

所以O(n log(n))是一个子集O(log(n!)).

因为O(n log(n)) ? O(log(n!)) ? O(n log(n)),他们是相当的大哦班.

Answer 2

通过斯特林的近似,

log(n!) = n log(n) - n + O(log(n))

对于大n,右侧由术语n log(n)支配.这意味着O(log(n!))= O(n log(n)).

更正式地说,"大O"的一个定义是f(x)= O(g(x))当且仅当

lim sup|f(x)/g(x)| < ? as x ? ?

使用斯特林的近似,使用此定义很容易显示log(n!)∈O(n log(n)).

类似的论点适用于n!.通过取斯特林近似两边的指数,我们发现,对于大n,n!行为渐近地像n ^(n + 1)/ exp(n).由于n/exp(n)→0为n→∞,我们可以得出n!∈O(n ^ n)但O(n!)不等于O(n ^ n).O(n ^ n)中的函数不在O(n!)中(例如n ^ n本身).