algorithm - O(m+n) 与 O(m) /O(n)

Question

不同的算法有不同的时间复杂度。我对这个太好奇了。

O(m+n) 表示线性函数，与 O(m) 或 O(n) 类似，它们也表示线性函数。O(m+n) 与 O(m) 或 O(n) 有何不同？它们都代表线性时间。在 O(n)/O(m) 的情况下，我们忽略其他项，只取最高次数。即使在以下等式的情况下：T(n)=n+1+n+1；我们使 T(n)=2n 并因此使其成为 O(n)。无论如何，我们没有考虑等式的其他部分。

我确实读过一些关于这方面的文章，但我不太明白这些是什么意思，因为根据那些文章（或者我可能误解了），m 和 n 代表两个变量 i 和 j，但如果是这样，那我们为什么要将两指针算法写为 O(n^2)。

这一切让我很困惑，请向我解释其中的区别。

标签： algorithmbig-o

Answer 1

m并且n可能具有非常不同的值，这就是为什么O(m+n)不同于O(m)or O(n)（但类似于O(max(m,n))）

简单示例：
图上的广度优先搜索具有复杂性O(V+E)，其中V顶点数E是边数。

因为稠密图E可能和 一样大V*(V-1)/2，所以E~V^2我们不能说复杂性是O(V) - 在这种情况下它是O(V^2)。

另一方面 - 非常稀疏的图，其中E与 相比非常小V。在这种情况下，我们不能这么说O(E)- 在这种情况下它是O(V)。

并且O(E+V)在所有情况下都有效。