algorithm - 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! 

第一个是通过将乘积中每个因子的上限设置为 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

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

如果您也不满意，我鼓励您阅读:https://en.wikipedia.org/wiki/Stirling%27s_approximation