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

外部的另一个提示for(int i=1;i<=n;i*=2)：每次执行for循环体后，将i乘以 2：

1 · 2 · 2 · … · 2

只要条件为真，这就会重复：

1 · 2 · 2 · … · 2 ≤ n

我们还可以将 2 的重复乘法写成如下：

2 · 2 · … · 2 = 2 ^x ≤ n

i乘以 2的次数，即x，可以用以 2 为底的对数计算，即 log ₂ ( n )：

2 ^x ≤ n

使用x = log ₂ ( n ) 它实际上是相等的：

2^{日志₂ ( n )} = n

因此for条件是 floor(log ₂ ( n )) 乘以 true，因此其复杂度是 Ο(log( n ))、Ω(log( n ))，因此是 θ(log( n ))。