O(n Log n) 是多项式时间吗？如果是这样，你能解释一下为什么吗？
我对数学证明感兴趣，但我也会感谢任何强烈的直觉。
谢谢！
问问题
22180 次
4 回答
17
是的，O(nlogn) 是多项式时间。
来自http://mathworld.wolfram.com/PolynomialTime.html，
如果对于某个非负整数 m，完成给定输入的算法所需的步数为 O(n^m)，则称该算法可在多项式时间内求解，其中 n 是输入的复杂度。
来自http://en.wikipedia.org/wiki/Big_O_notation，
f 是 O(g) 当且
我现在将证明对于某些 m，n log n 是 O(n^m)，这意味着 n log n 是多项式时间。
确实，取 m=2。（这意味着我将证明 n log n 是 O(n^2)）
为证明，取 k=2。（这可以更小，但不是必须的。）存在一个 n_0 使得对于所有较大的 n 以下成立。
n_0 * f(n) <= g(n) * k
取 n_0 = 1（这就足够了） 现在很容易看出
n log n <= 2n*n
日志 n <= 2n
n > 0（假设）
如果您对此不确定，请单击此处。
这个证明在乳胶数学模式下可能会更好，但我认为 stackoverflow 不支持这一点。
于 2013-11-09T22:47:41.347 回答
5
是的，因为它的上限是多项式 (n)。您可以看一下图表并从那里开始，但除此之外我无法制定数学证明：P
编辑：从维基百科页面，“如果算法的运行时间是算法输入大小的多项式表达式的上限，则称该算法具有多项式时间”。
于 2013-11-09T22:41:00.437 回答
4
它至少不比多项式时间差。仍然不是更好：n < n log n < n*n。
于 2013-11-09T22:36:32.007 回答
-1
是的。当 n 趋于无穷时，nlogn 的极限是多少？直观上，对于较大的 n，n >> logn 并且您可以考虑以 n 为主的乘积，因此 nlogn ~ n，这显然是多项式时间。更严格的证明是使用 Inspired 所做的三明治定理：
n^1 < nlogn < n^2。
因此，nlogn 由一个多项式时间的序列限定在上方（和下方）。
于 2013-11-09T22:44:02.703 回答