While 循环中包含收缩列表的算法的大 O 表示法

Question

我试图估计一个看起来像这样的算法的最坏情况（评论中的估计复杂度是我的，其中 V 是顶点数，E 是图中边的数量):

while(nodes.size()!=0) { // O(V) in which nodes is a LinkedList
     Vertex u = Collections.min(nodes); // O(V)
     nodes.remove(u); // O(1)
     for(Map.Entry<Vertex, Integer> adjacency : u.adj.entrySet()) { // O(E)
         // Some O(1) Statement

         if(nodes.contains(v)) { // O(V)
            // Some O(1) Statement
         }
     }
}

我的问题很简单：在 while 循环中的每一轮之后， nodes LinkedList 将变得越来越小。最终，Collections.min() 和 nodes.contains() 操作每轮都将花费更少的时间。

我的理解是Big O Notation总是认为最差，因此上面的复杂性应该是正确的。

否则，请您解释一下如何在上述场景中计算出正确复杂度的情节？

Answer 1

是的，这些看起来是正确的。将它们放在一起你会得到时间O(V*(V+E))。（更正，O((1+E)*V^2) - 我错过了 O(E) 内部循环中的 O(V)。）

不过，对您的理解有一个重要的更正。大 O 符号并不总是最坏的情况。该符号是一种估计数学函数增长的方法。这些功能是最坏情况还是平均情况，或者它们测量的是什么完全取决于手头的问题。例如，快速排序可以在 O(n^2) 最坏情况运行时间内实现，平均 O(n log(n)) 时间运行，平均使用 O(log(n)) 额外内存和 O(n) 最坏情况下的额外内存。

Answer 2

您可以在每一步取最大可能值，但这可能会导致最终值过高估计。为确保值准确，您可以将上限留到最后，但通常最终结果都是一样的。

当V的值发生变化时，再引入另一个变量v，它是一个特定迭代的值。那么每次迭代的复杂度为v+(E*v)。那么总复杂度就是每次迭代的总和：

sum(v = 1...V) v+(E*v)
= 1+1E + 2+2E + 3+3E + ... + V+VE                 - Expand the sum
= (1 + 2 + 3 + ... + V) + (1 + 2 + 3 + ... + V)E  - Regroup terms
= (V^2 + V)/2 + (V^2 + V)E/2                      - Sum of arithmetic series
= (V^2 + V + EV^2 + EV)/2                         - Addition of fractions
= O(EV^2)                                         - EV^2 greater than all other terms

Answer 3

nodes.contains 在 Θ(V) 中具有最坏情况时间复杂度，for 循环在 Θ(E) 中运行多次，因此在 [=13] 中具有最坏情况时间复杂度=], Collections.min 在 Θ(V) 中具有最坏情况时间复杂度，因此 while 循环体在 Θ(V+V*E) 中具有最坏情况时间复杂度，但 V+V*E 本身是 Θ(V*E)（见后面），因此 while 循环体的最坏情况时间复杂度为 Θ(V*E)。 while 循环执行 V 次。所以执行算法的最坏情况时间在 Θ(V^2*E).

那里的简化——用Θ(V*E)替换Θ(V+V*E)——是可以接受的，因为我们正在研究V>1的一般情况。也就是说，V*E 总是比 V 大，所以我们可以将 V 吸收到一个有界常数因子中。说最差时间在 Θ(V^2+E*V^2) 中也是正确的，但人们不会使用它，因为简化形式更有用。

顺便说一句，凭直觉，您通常可以忽略算法中容器 "used up" 的影响，例如插入排序要查看的项目越来越少，或者该算法具有更少的扫描的节点更少。这些影响变成常数因素并消失。只有当您每次都消除 有趣数量 的元素时，例如使用快速选择算法或二进制搜索，这类事情才会开始影响渐近运行时。

While 循环中包含收缩列表的算法的大 O 表示法

Big O Notation For An Algorithm That Contains A Shrinking List Inside While Loop

algorithm

time-complexity

big-o

graph-algorithm

asymptotic-complexity