嵌套循环每次变化的算法复杂度

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
    }
  }
}

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。