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

Question

任何人都可以让我告诉我以下代码的大 O 时间复杂度:

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的次数executes 等于从 1 到 n-1 的数字之和.那笔款项是 n*(n-1)/2 ，它在 Theta(n^2) 中，因此也在 O(n^2) 中。