algorithm - 什么是 O(n*log m) + O(m)？

Question

我对大 O 符号的加法感到困惑。

我要创建一种算法来为具有学校问题的其他一些要求的图找到 MST。它的时间复杂度为 O(E * log V)，其中 E 是图中的边数，V 是图中的顶点数。我已经找到了一个解决方案，它的复杂度为 O(E * log V) + O(V)。

O(E * log V) + O(V) = O(E * log V) 是否成立？

谢谢大家的回答!我假设连接图和非连接图的这种复杂性，我的算法在 O(E * log V) 内运行。

Answer 1

对于任何 x，您可以制作一个具有 x 条边和 2ˣ 个(大部分不连接的)顶点的图。

对于这样的图，E log V = x²，所以 (V + E log V)/(E log V) = (2ˣ+x²)/x²。

它随着 x 的增加而无限制地增长，因此 O(E log V) + O(V) 与 O(E log V) 不同，即使对于图形也是如此。

但是，如果您指定连通图，那么您有 V < E。在这种情况下，只要 V>=2，您就有 V + E log V < E + E log V <= 2(E log V)

所以对于连通图，O(E log V) = O(E log V) + O(V)。