为什么 m 不能在 O(n^2 +m) 中去掉？

Question

既然大O是代码如何缩放的度量，n^2的扩展速度不应该比m快得多吗？我不明白具体值是如何相关的

Answer 1

有时，复杂性和大O具有，或者更确切地说取决于两个变量。例如，许多图形算法使用E和V作为边和顶点的数量。如果m是常数或从n导出，那么通常的分析可以允许减少它。然而，我们可以想象(可能是人为的(情况是，比如 m=n^3，因此比m^2项的阶数更高。

我举的一个人为的例子是有一个包含n个元素的数组N和一个包含m个元素的巨大列表M来检查元素是否在第一个数组中。我们天真地选择使用气泡排序(O n^2(，并对排序数组N对M中的每个元素使用二叉搜索。

我们将有O(n^2+ m + log(n( (。将log n减少为较低数量级后，我们最终得到O(n^2+m(。

我们可以将交叉自连接而不是自行车类型的数组，必须检查 m 次。