问n^2对数n复杂度

EN

如果这是算法的时间复杂度，那么它已经是大O表示法了，所以，是的，保持日志。渐近地说，O(n^2)和O((n^2)*log(n))是有区别的。

正式的数学证明在这里会很好。

让我们定义以下变量和函数：

N -算法的输入长度，

f(N) = N^2*ln(N) -一个计算算法执行时间的函数。

让我们确定这个函数的增长是否是O(N^2)渐近有界的。

根据渐近表示法[1]的定义，g(x)是f(x)的一个渐近界当且仅当:对于所有x的足够大的值，f(x)的绝对值至多是g(x)的正常数倍数。也就是说，f(x) = O(g(x))当且仅当存在一个正数M和一个实数x0，使得

|f(x)| <= M*g(x) for all x >= x0 (1)

在我们的例子中，必须存在一个正实数M和一个实数N0，以便：|N^2*ln(N)| <= M*N^2 for all N >= N0 (2)。

显然，这样的M和x0不存在，因为对于任意的大型M，存在N0，例如ln(N) > M for all N >= N0 (3)

因此，我们证明了N^2*ln(N)不是O(N^2)渐近有界的。

参考文献：

1：- 符号表示法

理解大O表示法的一个简单方法是将原子步骤的实际数目除以使用大O的术语，并验证得到一个常量(或小于某个常量的值)。

例如，如果算法执行10n 2的⋅logn步骤：

10平方公里的-> logn/n 2=10 log n⋅logn不恒定于n -> 10平方公里的⋅log n不是O(N 2)

10n ->⋅logn/(n⋅logn)= 10⋅常数n -> 10 2⋅log n is O(n 2⋅logn)