algorithm - 每次嵌套循环都在变化的算法的复杂性

Question

我必须说出以下两种算法的复杂性:

for ( i=1; i < n; i *= 2 ) {
  for ( j = n; j > 0; j /= 2 ) {
    for ( k = j; k < n; k += 2 ) {
      sum += (i + j * k );
    }
  }
}

for( int i = n; i > 0; i-- ) {
  for( int j = 1; j < n; j *= 2 ) {
    for( int k = 0; k < j; k++ ) {
       ... // some operation
    }
  }
}

在第一个例子中，我知道外循环和中循环的复杂度是 log(n)，但我不知道如何计算内循环的复杂度，因为 k 的初始化在迭代时发生变化

对于第二个，显然复杂度是n^2，但我真的不明白为什么

Answer 1

如您所说，外层循环是log(n)，其参数i 不用于内层循环。对于另外两个内部循环:

 value of j    iteration number of the most inner loop
 j = n;        k: 0 
 j = n/2;      k: (n - n/2)/2
 j = n/4;      k: (n-n/4)/2

因此，总和为 ((1-1/2) + (1-1/4) + (1-1/8) + ... + (1-1/2^log(n )))n/2 = (log(n) - c) * n/2 = Theta(n log(n))。因此，总复杂度为 n (log(n))^2。