4

私は coursera でアルゴリズムのコースを受講していますが、この特定の問題で立ち往生しています。このコードの時間計算量を見つけることになっています。

int sum = 0

 for (int i = 1; i <= N*N; i = i*2)

  {
     for (int j = 0; j < i; j++)
           sum++; 
  }

私は日食自体でそれをチェックしました. N の任意の値に対して、合計ステートメントが実行される回数は N 未満です

final value of sum:
for N=8 sum=3 
for N=16 sum=7 
for N=100000 sum=511

したがって、時間計算量は N 未満である必要がありますが、与えられた答えは N の 2 乗です。どうしてそれが可能なのでしょうか?

私がこれまでに行ったこと：

最初のループは log(N^ 2) 回実行され、その結果、2 番目のループは 1,2,3.. 2 logN を実行します。

4

4 に答える 4

3

ここには多くの混乱がありますが、重要なことは、Big-O 表記法はすべて成長率、または数学者が言うように行動を制限することです。関数が O(n*n) で実行されるということは、実行時間がたとえば n よりも速く増加するが、たとえば2 ^nよりも遅くなることを意味します。

big-O 表記法で推論するときは、定数は「数えない」ことに注意してください。この特定の質問にはいくつかの癖があります。

  • ループが通常のN*Nfor ループである場合、式自体は O(log n*n) の複雑さにつながります...
  • ...ただし、for ループのインクリメントi = i*2により、外側のループが約 log n 実行され、内側のループの内容がnに依存しない時間で実行される場合、関数は O(log n) になります。
  • ただし、繰り返しますが、内側のループの実行時間はnに依存しますが、n*n の実行は行わず、おおよそ (n*n)/2 のループをログに記録します。「定数はカウントされない」ことと、最終的には O(n*n) になることを思い出してください。

これで問題が解決することを願っています。

于 2012-08-12T19:52:19.400 に答える
3

最初の内部ループは 1 + 2 + 4 + 8 .. 2^M で、2^M は <= N * N です。

N * N までの 2 のべき乗の合計は、およそ 2 * N * N または O(N ^ 2) です。

注: N=100000 の場合、 N*N はオーバーフローするため、結果は誤解を招きます。オーバーフローが問題の一部であると考える場合、合計は大きな数に対してかなりランダムであるため、その O(1) を主張できます。つまり、N=2^15、N^2 = 2^30 の場合、合計は整数になります。 .MAX_VALUE. N の値が大きくなっても、合計が大きくなることはありません。

于 2012-08-12T19:50:41.083 に答える
2

したがって、合計++は1 + 2 + 4 + 8 + ... + N * N、合計log2（N * N）回実行されます。等比数列の合計1*（1-2 ^ log2（N * N）/（1-2）= O（N * N）。

于 2012-08-12T20:13:34.277 に答える
0

外側のループは log(N^2)->2*log(N)->log(N) で、内側のループは N^2/2->N^2 です。したがって、時間計算量は N^2*log(N) です。

ベンチマークについては、N=8 または N=16 の値はばかげており、ループ内の時間は JVM の設定に関連してわずかであり、キャッシュが失敗するなどです。絶対です：

最大の N から始めて、それがどのように評価されるかを確認します。

N の各値で複数の実行を行います。

時間計算量は、N が非常に大きくなったときにアルゴリズムがどのように機能するかの尺度であると考えてください。

于 2012-08-12T19:51:37.950 に答える