嵌套j = i + 1循环的大O时间复杂度

Question

任何人都可以告诉我下面这段代码的时间复杂度:

for (int i = 0; i < array.length - 1; i++) {
    for (int j = i + 1; j < array.length; j++) {
        // do something
    }
}

它不可能是O(n^2)从那以后j = i + 1？谢谢!

Answer 1

有n-1外循环的迭代.在每次迭代中,内部循环迭代n-i-1次数.所以总的来说内循环迭代n-1 + n-2 + ... + 1次数.因此do something执行的次数等于1到1之间的数字之和n-1.该总和是n*(n-1)/2在Theta(n ^ 2)中,因此也在O(n ^ 2)中.