n阶乘时间函数的正确时间复杂度是多少？

Question

我对这个话题很陌生，我正试图掌握与渐近符号相关的一切。我想就以下问题征求你的意见:

如果我们有，对于一个算法，T（n）=n！，那么我们可以说它的时间复杂度：

1 x 1 x 1 ... x1 <= n! <= n x n x n ... x n

这个关系意味着n！=O（n^n）和n！=ω（1）。然而，我们不能做得更好吗？我们希望big-oh尽可能接近函数T（n）。如果我们做以下操作：

n! <= 1 x 2 x 3 x 4 ... x n x n

也就是说，对于倒数第二个元素，我们将 （n-1） 替换为 n。现在这种关系不是真的吗？那么n不是真的吗！= O（1 x 2 ...x n x n）？对于下限Ω也可以这样说。

我不确定我的过程中是否有错误，所以我非常感谢您的意见。提前谢谢。

Answer 1

数学语句n！=O（1 x 2… x n x n）是正确的。但也没有什么帮助或启发。在什么情况下你想写n！=O（…）？

要么您对n！=满意n，并且不需要编写n！=O（1 x 2…x n x n）。或者您对n！=不满意n ；您需要更好地解释n的大小 ；那么你不应该满足于n！=O（1 x 2…x n x n），因为它并不容易理解。

我个人对多项式比较满意，像n^2.我对指数很满意，比如2^n.我对n^n也有些满意，因为我知道n^n = 2^(n log n)，我也知道我不能希望为n^n.找到一个更好的表达

但我对n不满意 。我希望能够将其与指数进行比较。

这里有两个对比:

n! < n^n
2^n < n! 

第一个是通过将乘积中的每个因子增加< code>n得到的；第二个是通过将乘积中的每个因子降低< code>2得到的。

这已经很好了。它告诉我们< code>n！介于指数2^n和超指数n^n.之间

但是你可以很容易地看出上限n^n太高了;例如，您可以非常轻松地找到以下更严格的界限：

n! < n^(n-1)
n! < 2 * n^(n-2)
n! < 6 * n^(n-3)

请注意，当n很大时，n^（n-3）比n^n小很多！这稍微好一点，但仍然不令人满意。

您可以走得更远，并注意到一半的因子小于n/2，因此：

n! < (n/2)^(n/2) * n^(n/2) = (1/2)^(n/2) * n^n = (n / sqrt(2))^n =~ (0.7 n)^n

这是一个稍微紧一点的上限！但是我们能做得更好吗？我还是不满意。

如果你也不满意，我鼓励你阅读：https：//en.wikipedia.org/wiki/Stirling's_approximation