0

次のコードの big o 表記の計算について質問があります。

j = 1;
while ( j <= n ) do  
  for i = 1 to j do 
    O(1); 
  endfor; 
  j=j*2; 
endwhile

これまでのところ、ループは Σ i=1,..,n 2 iと計算されています。幾何学的数列のように見えますが、大きな O の値がどうなるかはわかりません。誰でも助けてもらえますか？

4

5 に答える 5

3

すでに述べたように幾何学的シーケンスであるため、ここではガウスではありません。

j が n に達すると、外側の while ループは停止します。

そのために必要な反復回数は、ここで解決するlog₂(n)問題2^x = nであると仮定して計算できます。(nに達するまで何回2を掛け続けなければならないか)

興味深いことに、これは次のことにつながります。

log₂(n)     log₂(n)
∑ 2^i    =  2       - 1 = n - 1
0

Sum from 1 to log2(n) taken over 2^iこれはまさに2^(log2n) - 1= n - 1(フォントセットが必要な Unicode 文字をサポートしていない場合に備えて、上記の式を言い換えます)

ここでの事実を利用して

k            k+1
∑ 2^i    =  2   - 1
0

したがって、アルゴリズムはO(n)にする必要があります。

または、幾何学的シーケンスの一般的な式を使用して合計を計算することもできます。

Sn = a0 * (1-q^n) / (1-q)

これは、実際には同じ結果につながるはずです。

        log₂n
   1 - 2           1 - n
  -----------  =  ------ = n - 1
    1 - 2           -1
于 2013-03-29T01:33:50.917 に答える
0

0(n^2) である必要があります。これは挿入ソートと同じです

void insertionsort(void){

 for(int x=1;x<n;x++){
   int temp= array[x];
   for(int y=x-1;  y>=0 && array[y]>temp ;y--){
    array[y+1]=array[y];
   }array[y+1]=temp;
 }
}

1 から n になると O(n) になりますが、それぞれ y=x-1 から 0 になります。最悪の場合、常に y=x-1 から 0 になります。したがって、これはx が大きくなるたびに。

これはあなたの場合です。

于 2013-06-16T11:02:14.527 に答える
0

幾何学的順序は正しいです。簡単な例を見てみましょう。n が 8 の場合、内側のループの反復回数は 1、次に 2、次に 4、次に 8 です。n が 7 の場合、1、2、4、そして 8 はありません。したがって、O( 1) n を増やすと、操作は n と 2n - 1 の間で変化します。その範囲の両側で、次数は O(n) です。

于 2013-03-29T01:28:59.033 に答える
0

わかりました! 理解を深めるために、いくつかの値を想定してみましょう。

n を 4 とします。

So now:
j=1 ( <4 ) => loop runs 1 time = O(1)
j=1*2 = 2 ( <4 ) => loop runs 2 times = 2*O(1)
j=2*2 = 4 ( =4 ) => loop runs 4 times = 4*O(1)

n が 2^x 型の場合、一連のループ実行は次のようになります。

O(1) + 2*O(1) + 4*O(1) + 8*O(1) + 16*O(1) + ..... + n*O(1). = 1*(2^(x+1) - 1)*O(1)/(2-1) = (2n-1)*O(1) = O(n) n = 2^x で、外側のループは x+1 回実行されます。

n が 2^x 型でない場合。n = 6 としましょう。

So now:
j=1 ( <6 ) => loop runs 1 time = O(1)
j=1*2 = 2 ( <6 ) => loop runs 2 times = 2*O(1)
j=2*2 = 4 ( <6 ) => loop runs 4 times = 4*O(1)
j=2*4 = 8 ( >6 ) => loop exits.

外側のループが 2^( floor value( log base 2(n) )) + 1 回だけ実行されることは明らかです。そして、この値は有効な n になります。

したがって、式に入れましょう: (2n-1) O(1) => (2 (2^(floorValue(logBase2(n))) - 1)*O(1) は O(n) にほぼ等しくなります。

于 2013-03-29T01:37:22.810 に答える
0

ここで少し賢くなるために: あなたが求めているのは、実際にはTheta. あなたのコードはTheta(n)- ですが、 Big-O は上限にすぎないO(n)ため、O(n * log_2(n))またはです。正確です。O(n!)Theta

于 2013-03-29T01:40:36.267 に答える