for-loop - for ループのランタイム

Question

このネストされた for ループのビッグ O 表記の実行時間は?

for(i = 1 to k)
{
    for(j = i+1 to k)
    {}
}

O(k^2) より小さいですが、わかりません。

Answer 1

あなたの質問は、シリーズ合計S(k) = 0 + 1 + 2 + ... + (k-2) + (k-1)と密接に関連しています。S(k) = (k*(k-1))/2 = (k*k)/2 - k/2 であることがわかります。 [どのように？合計をS(k) = {0+(k-1)} + {1+(k-2)} + {2+(k-3)} + ...のように並べ替え ます。これはその方法を示しています。]

したがって、アルゴリズムの次数はO(k*k)よりも小さいでしょうか? 1/2の ような定数係数はビッグ O 表記に影響しないことに注意してください。

質問: ? に置き換えるのj = i+1 to kと同じです。j = 1 to k

答え: そうですね。これは難しいので、よく考えてみましょう。の場合i == 1、内側のループのアクションは何回実行されますか? 回答:k-1回実行されます。繰り返しますが、 for のi == 2場合、内側のループのアクションは何回実行されますか? 回答:k-2回実行されます。最終的に、 fori == kの内側のループのアクションは何回実行されますか? 答え: ゼロ回実行されます。したがって、 のすべての値に対してi、内側のループのアクションは何回実行されますか? 答え: (k-1) + (k-2) + ... + 0、これは前述の合計S(k)です。