1 つ目は簡単です (2 つ目のコード スナップのツールを使用しますが、これは少しトリッキーです)。2 つ目のコード スナップに焦点を当てます。
Big O表記は、アルゴリズムが実行する操作の数に漸近的な上限を与えています。
各内部反復が 1 つの op を実行すると仮定し、カウンターとループのオーバーヘッドを無視しましょう。
プログラムT(n)
で実行された操作の総数を示します。
プログラムにこれ以上の操作がないことは明らかです。
// loop 1
for(int i = 0; i < n; i++)
// loop 2
for(int j = i+1; j > i; j--) //note a single op in here, see (1) for details
// loop 3
for(int k = n; k > 0; k--) //we change k > j to j > 0 - for details see (2)
sum++;
(1)j
は として初期化されi+1
、繰り返しごとに減少するため、ループ 2 の最初の繰り返しの後、 が得られj == i
、条件は false になります。つまり、1 回の繰り返しが行われます
(2) 元のループは次のn
回数以上繰り返されません。 (以来j >= 0
) - したがって、「新しいプログラム」は古いプログラムよりも「良くない」(上限に関して)。
単純化されたプログラム
の複雑さ ループ 1 とループ 3 はそれぞれ何度も繰り返され、ループ2 は正確に 1 回
繰り返されるため
、上記のプログラムの全体的な複雑さはです。内側のループごとに 1 つのコマンドが実行されると仮定すると、実行されるコマンドの総数は になります。O(n^2)
n
n^2
結論:
新しいプログラムはn^2
(仮定によると)「ops」を実行しており、元のプログラムは「新しいプログラムよりも悪くない」ため、ステップを実行していT(n) <= n^2
ます。
ビッグ O 表記の定義(c=1 で N ごと) から、プログラムは次のように結論付けることができます
。O(n^2)