algorithm - 1 2 4 8 パターンのアルゴリズムの複雑さを計算する

Question

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

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 .. .)

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

Answer 1

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

このコード:

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

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

for(int j=i; j<=i*i; j += i)
    // ... blah ...

Answer 2

外側のもう 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 ₂ ( n )で計算できます。

2 ^× ≦ n

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

2 ^{log ₂ ( n )} = n

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