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).

Answer 2

提示：写一个方程，描述组合的数量作为集合大小的函数。

删除任何低阶项并忽略最高阶项中的任何常数乘数。