什么是 O(n*log m) + O(m)？
What is O(n*log m) + O(m)?
我对大 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).
中工作
对于任意 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) 不同，即使对于图形也是如此。
但是，如果您指定 connected 图，那么您有 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) 已连接 图。
O(ElogV+V) 与 O(ElogV) 不同。一般来说V可以比ElogV任意大，这使得两者的复杂度类不同。
但是，假设您有一个 O(ElogV + V) 时间算法来查找 MST（如果存在的话），您可以将它变成一个有保证的 O(ElogV) 时间算法，假设图形以邻接列表形式表示.
我们可以在O(E)时间内确定是否E>=V/2。遍历图形的顶点，看看是否有任何边与该顶点相邻。如果您发现没有相邻边的顶点，则该图显然没有 MST，因为该顶点未连接到图的其余部分。如果你遍历了所有的顶点，你就知道E>=V/2。如果你在 n 步后找到一个没有相邻边的顶点，你知道你在图中至少有 (n-1)/2 条边，所以这个过程需要 O(E) 时间（即使天真地看起来它是 O(五）时间）。
如果E小于V/2，则图断开（因为在连通图中，E>=V-1），没有MST。
因此：检查是否 E>=V/2 并且仅当是时，运行 您的 MST 算法。
这需要 O(E + ElogV + V) = O(E + ElogV + 2E) = O(ElogV) 时间。
我对大 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).
中工作对于任意 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) 不同，即使对于图形也是如此。
但是，如果您指定 connected 图，那么您有 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) 已连接 图。
O(ElogV+V) 与 O(ElogV) 不同。一般来说V可以比ElogV任意大，这使得两者的复杂度类不同。
但是，假设您有一个 O(ElogV + V) 时间算法来查找 MST（如果存在的话），您可以将它变成一个有保证的 O(ElogV) 时间算法，假设图形以邻接列表形式表示.
我们可以在O(E)时间内确定是否E>=V/2。遍历图形的顶点，看看是否有任何边与该顶点相邻。如果您发现没有相邻边的顶点，则该图显然没有 MST，因为该顶点未连接到图的其余部分。如果你遍历了所有的顶点，你就知道E>=V/2。如果你在 n 步后找到一个没有相邻边的顶点，你知道你在图中至少有 (n-1)/2 条边，所以这个过程需要 O(E) 时间（即使天真地看起来它是 O(五）时间）。
如果E小于V/2，则图断开（因为在连通图中，E>=V-1），没有MST。
因此：检查是否 E>=V/2 并且仅当是时，运行 您的 MST 算法。
这需要 O(E + ElogV + V) = O(E + ElogV + 2E) = O(ElogV) 时间。