4

このアルゴリズムの複雑さを計算する必要があります:

f=1;
x=2;

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

i^2(i(i+1)/2) である内部ループのパターンと合計を計算しましたが、(1 2 4 8 16 .. .)

では、この系列の総和を求めるにはどうすればよいでしょうか。

4

2 に答える 2

3

私はあなたのためにこれを解決するつもりはありません (これは宿題のようです)。しかし、ここに問題を単純化するためのヒントがあります。

このコード:

for(int j=1; j<=i*i; j++)   
    if(j%i==0)
        // ... blah ...

は、次のコードと同等です。

for(int j=i; j<=i*i; j += i)
    // ... blah ...
于 2012-05-03T14:37:22.080 に答える
1

外側のもう 1 つのヒント:ループfor(int i=1;i<=n;i*=2)の本体を実行するたびに、 iに 2 が乗算されます。for

1・2・2・…・2

これは、条件が真である限り繰り返されます。

1・2・2・…・2≦ n

2 の繰り返し乗算は、次のように書くこともできます。

2・2・…・2=2 ×n

iが 2 で乗算される回数、つまりxは、2 を底とする対数、つまり log 2 ( n )で計算できます。

2 ×n

x = log 2 ( n ) を使用すると、実際には等しくなります。

2 log 2 ( n ) = n

したがって、for条件は floor(log 2 ( n )) 回 true であるため、その複雑さは Ο(log( n ))、Ω(log( n ))、したがって θ(log( n )) です。

于 2012-05-26T18:04:15.663 に答える