0

みんなと率直に話すために、これは宿題です。誰かが私に何度も答えを出してくれるとは思っていません。これは、私が物事を正しく理解していることを確認するため、または私が間違っていることを理解するためです.

Big-Oh がどのようなものになるかを判断するために、いくつかのコードの断片が与えられました。それぞれが for ループを扱っていますが、与えられた最後の 2 つは少し気が遠くなります。最初：

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

これのビッグオーはO(n^4)だと思います。#1 は n 回実行され、#2 は n^2 回実行され、#3 は n 回実行され、n^4 になります。ただし、これを C++ で適切に記述し、n 値を 10、100、および 1000 に指定すると (割り当てに従って)、n = 10 は 7524 を返します (良い、10,000 未満) n = 100 は 975,002,490 の値を返しますが、上限は100,000,000になります。明らかに、私はループの分析のどこかから外れていますが、どこにあるのかよくわかりません。n = 1000 が何を返すかはわかりません。私のコンピューターはしばらく処理を続けていて、まだ答えを出す準備ができていないようです。

2 番目のフラグメントは次のとおりです。

   sum = 0;
      for (i = 0; i < n; i++) //1
         for (j = 0; j < i * i; j++) //2
            if (j % i == 0) //3
               for (k = 0; k < j; k++) //4
                  sum++;

if ステートメントの実行時間はテストの実行時間とその内容の合計になるため、if ステートメントを安全に無視できると思います。つまり、再び O(n^4) を考え出すことになります。

4

1 に答える 1

0

私は O の専門家ではありませんが、for ループといくつかの数学を知っているので、少しお手伝いします。

「#1 は n 回実行され、#2 は n^2 回実行され、#3 は n 回実行され、n^4 回実行される」というステートメントを考慮すると、部分的にしか正しくありません。はい、次の場合、数値はほぼ正しいです。ループを別々に実行します。しかし、n = 4 の例を考えてみましょう...最初の #1 は 4 回実行されますが、ループ番号 #1 のループ番号 #2 の反復ごとに i*i 回実行されます...そう..

最初に i = 0 のとき #2 は 0 回実行されます.. (j < 0*0) 次に i = 1 のとき #2 は 1 回実行されます (j < 1*1) そして i = 2 のとき #2 ループは 4 回実行されます(j < 2*2) で、i = 3 の場合 #2 は 9 回実行されます (j < 3*3)

したがって、合計 #2 は 14 回実行されます。(0 + 1 + 4 + 9 ) であり、4^4 は 14 ではありません。これも #3 ループにエスカレートします。

あなたが直接の答えには興味がないと言ったように、これが for ループをもう少しよく理解するのに役立つことを願っています.

于 2013-01-29T13:51:41.497 に答える