algorithm - 此循环的大 O 复杂度

Question

以下循环的大 O 复杂度是多少:

for each vertex u ∈ C do
        for each vertex v ∈ C and v > u do

我在这里做的是想象以下集合 {1,2,3,4} 循环为这个数字的 2 个元素的所有组合执行一个函数，(1,2)，(1,3) , (1,4), (2,3), (2,4), (3,4).

是否 =(n^2) 其中 n 是集合中元素的数量？

Answer 1

是的，这是O(n^2)，当然假设执行的函数是O(1)，迭代器也是O (1) 平均每次迭代(这通常是一个有效的假设)。

请注意，即使您进一步优化它，您也将处理 Choose(n,2) 元素，并且 Choose(n,2)=n(n-1)/2，仍在 O(n^2) 中。