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)。但是，我们不能做得更好吗？我们希望大 OH 尽可能接近函数 T(n)。如果我们执行以下操作：

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

也就是说，对于倒数第二个元素，我们将(n-1)替换为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!

第一个是乘积中每个因子上界n得到的；第二个是通过将产品中的每个因素下限2获得的。

已经很不错了；它告诉我们 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

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

What is the correct time complexity for n factorial time funcion?