big-o - ネストされた j = i + 1 ループの時間の複雑さ

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) にもあります。