algorithm - アルゴリズムの複雑さ (漸近的)

Question

このアルゴリズムの複雑さが O(n^2) であることを誰かが確認できますか?

a = 0
b = 0
c = n
while (b <= c)
{
    for (j = b; j<=c; j++)
    {
        a = j * j -2 * j + 3
    }
    b = b + 3
    c = c + 2
}

Answer 1

外側のループのたびに

while(b <= c)

実行すると、b と c は以前よりも 1 だけ近くなります。ただし、b と c は距離 n 離れて開始されるため、内側の for ループは n+1 回実行することから始まり、次に n 回実行し、次に n-1 回実行し、最終的に 1 回実行するまで続きます。そして、あなたのプログラムは終了します。したがって、実行時間は次のように比例します。

(n+1) + n + (n-1) + (n-2) + ... + 1

そして、増加する整数の式の合計を調べて、この合計が等しいことを確認できます

(n+2)(n+1)/2 = O(n^2)

実行時間は O(n^2) です