big-o - 嵌套 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 到 的数字之和n-1。这个总和是n*(n-1)/2，它在 Theta(n^2) 中，因此也在 O(n^2) 中。