0

先生は、基本的にループとネストされたループがある場合、操作の回数は次の n(n+1)/2 であると教えてくれました。

しかし、いくつかのプログラムを調べたところ、そうではない可能性が高いことに気付きました。

for(i=0, i<n, n++)
 for(j=i, j<n, j++)
 {x=i+j}

この場合、i=0、j=0、n++、j++、および x=i+j を無視して、n(n+1)/2 になりますが、次のようになります。

for(i=0, i<n, n++)
 for(j=0, j<n, j++)
 {x=i+j}

私が間違っていない限り、それはn ^ nでしょう。

2 つのループの操作数が n(n+1)/2 の場合を正確に教えてもらえますか? 私は今ちょっと混乱しています。

4

3 に答える 3

1

最初の例では、操作は何回も、n次に何回も行われます。私の記憶が正しければ、これは ですが、あなたが正しい可能性もあり、それはです。いずれにせよ、それは非常に小さな違いです。n-1n-2n(n-1)/2n(n+1)/2

2番目の例では、何回もn、n何回も、n何回も... 何回も実行するまでn、nつまりn^2.

于 2013-05-09T02:19:14.510 に答える
0

あなたはおそらく先生を誤解した（または先生が間違えた）。n(n-1)/2は、一般的なループ ランタイムの一例にすぎません。あなたが観察したように、それは何でもかまいません。2番目の例にはn^2操作がありますが、別の一般的なパターンです。「n^n」の方がはるかにまれです。

于 2013-05-09T02:18:49.060 に答える
0 
for(i=0, i<n, n++)
 for(j=0, j<n, j++)
 {x=i+j}

最初のループはn時間を実行し、反復ごとに 2 番目のループを実行しnますn*n = n^2。

for(i=0, i<n, n++)
 for(j=i, j<n, j++)
 {x=i+j}

最初のループはn回実行され、反復ごとに 2(n-i)回目のループが実行されます....したがって、実行される回数x=i+jは1 + 2 + 3 ..... + n回であり、このシーケンスは最初のn整数の合計であり、これは次の式と同じです n(n+1)/2

于 2013-05-09T02:19:40.237 に答える