-6

次の各プログラム フラグメントについて、実行時間の Big-Oh 分析を行います。100% 確信が持てない問題が 2 つあります。誰か助けてください。

フラグメント 1:

for( int  i  =  0;  i  <  n;  i++ )
      for(  int  j  =  0;  j  <  n  *  n;  j++ )
            for(  int  k  =  0;  k  <  j;  k++ )
                 sum++;

回答: O(n^5) n*n はよくわかりません??

フラグメント 2:

for(  int  i  =  1;  i  <=  n;  i++ ) 
        for(  int  j  =  1;  j  <=  i  *  i;  j++ )
                             if (j % i == 0)
                   for(  int k  =  0;  k  <  j;  k++)
                  sum++;

答え:O(n^4)

4

2 に答える 2

0

ループごとに問題空間を分解します。最も外側のループから開始します。ループは実際に何をしているのですか？

最初の問題については、次のパターンがあります。

  • 外側のループはn回実行されます。
  • 外側の内側のループはn 2回実行され、内側のループの現在の値に拘束されません。
  • 最も内側のループはj回まで実行されるため、外側の内側のループの現在の値によってバインドされます。
  • すべてのステップは線形チャンクです。つまり、0 から終了状態まで線形に進みます。

実際に集計するとこんな感じ。

線形加算、スキップやステップオーバーはありません。

それで、それは何に翻訳されますか？合計を展開する必要があります。ただし、 O(n 5 ) にはなりません。

2 番目の問題については、次のパターンがあります。

  • 外側のループはn回まで実行されます。
  • 外側の内側のループはi 2回まで実行されます。
  • 最も内側のループは、次の条件でjj % i == 0回まで実行されます。つまり、最も内側のループが毎回実行されるわけではありません。

この問題はあなたに解決してもらいます。合計を展開し、それらを対応する代数に減らすというアプローチを取る必要があります。

于 2012-09-29T04:27:28.080 に答える
-1

フラグメント 1 の場合:

 lets say m = n^2
 Sigma(i=0...n)  m Sigma(j=0.....m) j
 => n * (m(m+1)/2)
 => n ^ 5

答え: O(n^5)

フラグメント 2 の場合:

last loop runs for i-1 times ...
Sigma(i=0...n)  Sigma(j=0.....i-1) Sigma(k=0.....j) k
approximately its Sigma(i=0...n) i^2 
~=> n^3

答え:O(n^3)

于 2012-09-29T04:34:20.297 に答える