每次删除一个元素的大 O

Question

你好，我正在尝试找出这个算法的大 O。

我认为是n^2，但是因为每次我不确定子循环的大小都在缩小。

 for(int i= 0; i < SIZE; i++){
        for(int j = i; j < SIZE; j++)
        {
            //Code here
        }
    }

Answer 1

是的，如果 SIZE = O(n) 并且（此处的代码）的复杂度是常数，则为 O(n^2)...

你可以算一下：对于固定的i值，内循环执行了Size-i次，因此内循环的总执行次数为sum_{i=0}^{size-1 } (size-i) = size^2 - sum_{i=0}^{size-1} i = size^2 - 1/2 size * (size-1) = O(size^2)

Answer 2

有一种使用 Sigma 表示法的方法足够精确：

Big O with removing an element each time