n^2 log n 复杂度

Question

我有点困惑。如果一个算法的时间复杂度给出为

那么在大 O 符号表示法中是仅为 还是要保留对数符号？

- darxsys

Answer 1

如果算法的时间复杂度已经是大O表示法了，那么是的，请保留log。从渐进角度来看，O(n^2) 和 O((n^2)*log(n)) 是有区别的。

- Martin Dinov

---

我完全同意这一点。虽然这似乎很明显，但我不断听到人们断言可以省略logN部分，因为它相对较小。这就是为什么我在下面添加了一个正式的数学证明。 - Alex T

@martin 请问，这个算法的时间复杂度是二次还是对数级别的？ - Gabe

@Jack，都不是。如果你有 O(log(n)) 的话，时间复杂度是对数级别的，如果你有O(n^2) 的话，时间复杂度是二次方级别的。如果你将它们相乘，就会得到超二次方时间（但低于立方级别）。 - Martin Dinov

Answer 2

这里需要一个正式的数学证明。

我们定义以下变量和函数：
N - 算法输入长度，
f(N) = N^2*ln(N) - 计算算法执行时间的函数。

让我们确定这个函数的增长是否渐进地受到 O(N^2) 的限制。

根据渐进符号 [1] 的定义，如果对于所有足够大的值 x，f(x) 的绝对值最多是 g(x) 的正常数倍，则 g(x) 是 f(x) 的渐进界。也就是说，当且仅当存在一个正实数 M 和一个实数 x0，使得

|f(x)| <= M*g(x) 对于所有 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：- https://en.wikipedia.org/wiki/Big_O_notation

- Alex T

Answer 3

理解大O符号的简单方法是将实际原子步骤数除以大O中的项，并验证你是否得到一个常数（或者比某个常数更小的值）。

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

10n²⋅logn/n² = 10 log n -> n没有常数 -> 10n²⋅log n不是O(n²)

10n²⋅logn/(n²⋅log n) = 10 -> n有常数 -> 10n²⋅log n是O(n²⋅logn)

- zvisofer

Answer 4

您需要记录日志，因为log(n)会随着n的增加而增加，并在乘法运算时增加整体复杂度。

通常情况下，只有当一个常数可以移除时才可以删除它。例如，如果您有O(2 * n^2)，则只需说复杂度为O(n^2)，因为在一台性能提升两倍的计算机上运行不应影响复杂度。

同样地，如果您的复杂度是O(n^2 + n^2)，则可以得到上述情况，只需说它是O(n^2)。由于O(log(n))比O(n^2)更优，如果您有O(n^2 + log(n)), 您应该说复杂度为O(n^2)，因为它甚至比O(2 * n^2)还要小。

O(n^2 * log(n))不符合上述情况，因此您不应将其简化。

- Vlad Schnakovszki

Answer 5

如果某个算法的复杂度为O(n^2)，则可以写成O(n*n)。但这并不等同于O(n)。因此，O(n^2*logn)不等同于O(n^2)。你需要知道的是O(n^2+logn)=O(n^2)。

- Tanmoy Banerjee

Answer 6

一个简单的解释： O(n2 + n) 可以写成 O(n2)，因为当我们增加 n 时，n2 + n 和 n2 之间的差异变得不存在。因此可以写成 O(n2)。

同时，在 O(n2logn) 中，随着 n 的增加，n2 和 n2logn 之间的差异会增加，不像上面的情况。 因此，logn 保持不变。

- Ranjeet Bansode