3 
sum = 0;
for(int i = 0; i < N; i++)
    for(int j = i; j >= 0; j--)
       sum++;

私が理解していることから、1 行目は 1 つの操作、2 行目は(i+1)操作、3 行目は(i-1)操作、4 行目はn操作です。これは、実行時間が になることを意味します1 + (i+1)(i-1) + nか? 私を混乱させるのは、これらの最後のステップだけです。

4

6 に答える 6

6

アルゴリズムを分析するために、「この特定の行がどれだけの時間に貢献しているか」を行ごとに尋ねたくないでしょう。その理由は、各行が同じ回数実行されないためです。たとえば、最初の行は 1 回だけ実行されるのに対し、最も内側の行は何度も実行されます。

このようなアルゴリズムを分析するには、値がアルゴリズムの合計実行時間の一定の係数内にある量を特定してみてください。この場合、その量はおそらく「行が何回sum++実行されるか?」になります。この値がわかれば、アルゴリズムの 2 つのループで費やされた合計時間がわかるからです。これを理解するために、これらのループで何が起こるかを追跡してみましょう。外側のループの最初の繰り返しで、i == 0内側のループが 1 回だけ実行されます (0 から 0 までカウントダウン)。外側のループの 2 回目の反復で、i == 1内側のループが正確に 2 回実行されます (最初は でj == 1、1 回は で実行されj == 0ます。より一般的には、外側のループの k 回目の反復で、内側のループが実行されます)。k + 1回。これは、最も内側のループの合計反復回数が次の式で与えられることを意味します。

1 + 2 + 3 + ... + N

この量は次のように示すことができます

N (N + 1)      N^2 + N    N^2    N
---------   =  ------- =  --- + ---
    2             2        2     2

これら 2 つの項のうち、このN^2 / 2項が支配的な成長項であるため、その定数要因を無視すると、実行時間は O(N 2 ) になります。

この回答を暗記する必要があると考えないでください。回答にたどり着くまでに必要なすべての手順を考えてください。カウントする量を見つけることから始め、その量がループの実行によってどのように影響を受けるかを確認しました。これから、その量の数式を導き出すことができ、それを単純化しました。最後に、結果の式を使用して、関数全体の big-O として機能する支配的な項を決定しました。

于 2011-01-29T23:11:01.263 に答える
2

裏返しに働きます。

sum++

これは繰り返されないため、それ自体が 1 つの操作です。

for(int j = i; j >= 0; j--)

これは i+1 回ループします。そこにはいくつかの操作がありますが、おそらく asm 命令の数を数えるつもりはありません。したがって、この質問では、これが i+1 の乗数であると仮定します。ループの内容は 1 回の操作であるため、ループとそのブロックは i+1 回の操作を実行します。

for(int i = 0; i < N; i++)

これは N 回ループします。前と同じように、これは N の乗数です。ブロックは i+1 操作を実行するため、このループは合計で N(N+1)/2 操作を実行します。そして、それがあなたの答えです！big-O の複雑さを考慮したい場合、これは O(N 2 ) に単純化されます。

于 2011-01-29T23:10:49.400 に答える
1

追加的ではありません。内側のループは、外側のループの繰り返しごとに 1 回発生します。つまり、O(n 2 ) です。

ところで、これはなぜこの種のものに漸近記法を使用するのかを示す良い例です。「操作」の定義に応じて、カウントの正確な詳細はかなり大きく変わる可能性があります。(sum++つまり、単一の操作add sum to 1 giving temp; load temp to sumですか?) しかし、定数因数にすべてを隠すことができることがわかっているので、それでも O(n 2 ) になります。

于 2011-01-29T23:05:58.007 に答える
0

いいえ; 各行の操作の特定の数を数えてから合計するわけではありません。「for」のような構造の要点は、特定のコード行を複数回実行できるようにすることです。N の関数として行 'sum++' が何回実行されるかを計算するには、思考と論理のスキルを使用する必要があります。ヒント: 3 行目に遭遇するたびに 1 回実行されます。

2 行目は何回出てきますか?

2 行目に遭遇するたびに、「i」の値が設定されます。3 行目はその値の i で何回実行されますか? したがって、全体で何回実行されますか? (ヒント: 何度か異なる金額をあなたに渡す場合、私があなたに渡した合計金額をどうやって調べますか?)

3 行目が検出されるたびに、4 行目が 1 回発生します。

どの行が最も頻繁に発生しますか? Nに関して、それはどのくらいの頻度で発生しますか?

于 2011-01-29T23:08:44.437 に答える
0

それでは、あなたが sum++ にどのような関心を持っているか、そしてそれを何回実行したかを推測してください。

sum の最終統計がその答えを示します。

実際、あなたのループは次のとおりです。

Sigma(n) n は 1 から N になります。

どれが等しいか:N*(N+1) / 2これにより、big-o-notation が得られますO(N^2)

また、質問の名前の横に、アルゴリズムに最悪のケースはありません。あるいは、最悪のケースは N が無限大になるときだと言えます。

于 2011-01-29T23:16:57.327 に答える
0

シグマ表記を使用してループを表す:

ここに画像の説明を入力

于 2014-04-23T22:17:49.663 に答える