ネストされたForループの実行時間見積もり/ビッグO表記

Question

いくつかのコードで実行された操作の数を表す関数f（x）の意味を理解できません。

int sum = 0; // + 1 
for (int i = 0; i < n; i++) 
    for (int j = 1; j <= i; j++) 
     sum = sum + 1; // n * (n + 1)/2 

（その最後のコメント上の分子には2が存在しないことに注意しますが、以下の機能にありますしてください。）

はその後、私のノートは言うF（X）= 2N（N + 2つのforループがあるので、f（x）が何であれ、= O（n^2）になりますが、それは何ですか？ jはどのようにして< =あなたにn *（n + 1）を与えるのですか？分母の2はどうですか？

Answer 1

このコードの実行全体を通して、内部ループが何回実行されるかを考えてみましょう。

• i = 0の場合、0回実行されます。
• i = 1の場合、1回実行されます。
• i = 2の場合、2回実行されます。
• i = 3の場合、3回実行されます。
• ...;
• i = n - 1の場合、n - 1回実行されます。

これは、合計回数は、最も内側のループは次式で与えられ実行されることを意味する

0 + 1 + 2 + 3 + 4 + ... +（N - 1）

これは有名合計であり、それは

0 + 1 + 2 + 3 + 4 + ... +（N - 1）

に解決= N（N - 1）/ 2

これはn - 1st triangular numberであり、これをメモリに記録する価値があります。

与えられた数字は - n（n + 1）/ 2 - は間違っているようですが、本当の数字にかなり近いです。ループは、0 + 1 + 2 + ... + n-1回ではなく、1 + 2 + 3 + ... + n回実行すると仮定していたと思います。

これより、O（n ）の語句がどこから来るのか分かりやすくなりました。 n（n - 1）/ 2 = n /2 - n/2であることに注意してください。