什么是O(log(n！))和O(n！)与斯特林近似 [英] What is O(log(n!)) and O(n!) and Stirling Approximation

问题描述

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

What is O(log(n!)) and O(n!)? I believe it is O(n log(n)) and O(n^n)? Why?

我认为这与斯特林逼近有关，但是我对它的解释不太清楚.

I think it has to do with Stirling Approximation, but I don't get the explanation very well.

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

Could someone correct me if I'm wrong (about O(log(n!) = O(n log(n)))? And if possible the math in simpler terms? I don't think I will need to prove that in reality I just want an idea of how this works.

推荐答案

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

O(n!) isn't equivalent to O(n^n). It is asymptotically less than O(n^n).

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

O(log(n!)) is equal to O(n log(n)). Here is one way to prove that:

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

Note that by using the log rule log(mn) = log(m) + log(n) we can see that:

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

So O(log(n!)) is a subset of O(n log(n))

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

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

大于(该表达式的左半部分用n/2替换的所有(n-x):

Which is greater than (the left half of that expression with all (n-x) replaced by 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!))的子集.

So O(n log(n)) is a subset of O(log(n!)).

自O(n log(n)) ⊆ O(log(n!)) ⊆ O(n log(n))起，它们是等效的big-Oh类.

Since O(n log(n)) ⊆ O(log(n!)) ⊆ O(n log(n)), they are equivalent big-Oh classes.

这篇关于什么是O(log(n！))和O(n！)与斯特林近似的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！