complexity-theory - 负多项式的 Big-O 复杂度

Question

我知道以下等式的大复杂度是 O(n^3)

4n^3 + 6n + 6

因为 n^3 是主导项。

对于相同的函数，big-o 复杂度是否相同，但系数为负？

-4n^3 + 6n + 6

Answer 1

实际上，如果您在大 O 计算中有否定项，您可以忽略它们，因为它们会让您赢得时间。

在这种情况下，复杂度将是O(n)。

虽然不知道这样的算法可以对应什么样的算法，但要回答一般问题，你可能会有类似的东西O(an^2 - bn)会带来O(n^2)复杂性。

编辑：

发现了一个有趣的相关问题，关于算法求解中的时间旅行。

Answer 2

形式上我们分析单调递增函数。渐近复杂性的正式定义暗示了这一点。

让我们看一下维基百科上的定义之一：

一个写

f(x) = O(g(x)) 作为 x -> inf

当且仅当存在一个正常数 M 使得对于所有足够大的 x 值，f(x) 至多 M 乘以 g(x) 的绝对值。也就是说，f(x) = O(g(x)) 当且仅当存在一个正实数 M 和一个实数 x0 使得

|f(x)| <= M|g(x)| 对于所有 x>x0

如您所见，此定义适用于绝对值。

在其他一些来源（例如有关数据结构和算法的书籍）中，您可能会发现没有绝对值的定义，但是在某处假设分析的函数是单调递增的（警告：有时假设隐藏在参考书目中或被分析宇宙的属性暗示）。

总结一下：渐近分析被设计用于单调递增函数。有时它由假设强制执行，有时由等式中的绝对值强制执行。

您可能会发现其他类似的说法，另一个 SO 答案，但结论相同。