V 循环中的每个 u,v 是否在 V 上呈线性？

Question

知道

for each u in V do // O(V)
     // ...

是否循环：

for each u,v in V do // O(V) or O(V^2)?
     // ...

在 V 或 V^2 上是线性的？

Answer 1

是O(V²)。更一般地说，有 Θ(n²) 对可以由一组 n 项组成，如果你迭代所有它们，只需将它们列出来就需要二次时间。