我对大 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) 不同,即使对于图形也是如此。
但是,如果您指定连通图,那么您有 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)。
关于algorithm - 什么是 O(n*log m) + O(m)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43608981/