嵌套循环的复杂性，外循环变量每次迭代减半

Question

void G(....) 
{
  for ( int k = n/2; k > 0; k /= 2 ) 
  { 
    for ( int m = 0; m < n; m++) 
      a[(k+m)%n]=k+m;
  }                      
}

当循环启动器和增量分别类似于 (n/2) 和 (k/=2) 时，我不确定如何计算循环操作......等等。运行编译器上针对不同 n 值的这段代码给了我有趣的结果，例如如果 n 是 2^x，那么对于 n 的值迭代是 n * x 直到 2^(x+1) -1。现在我卡住了，不知道将其归类为哪个 Big Oh 函数。欢迎大家answers/feedback/suggested学习methods/explanations！

Answer 1

外循环运行s for k = n / 2, n / 4, n / 8, ..., *。总共运行s Θ(log(n)) 次 - 这是将 n / 2 减少到 1 所需的顺序连续除以 2。

对于k的每个值，不考虑值，内层循环运行sn次，以此类推Θ(n) 时间内的内循环 + 主体运行。

由于无论外循环的值如何，内循环+主体都需要相同的时间，我们需要将外循环的次数运行s乘以运行ning内循环+主体的时间。这是 Θ(n log(n)).

嵌套循环的复杂性，外循环变量每次迭代减半

Complexity Of Nested Loop, With Outer Loop Variable Diminishing By Half Each Iteration

algorithm

big-o