复杂嵌套循环，利用外环可变逐渐缩小了一半每次迭代

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) respectively..and等。在编译器上运行此代码以获得不同的n值，例如，如果n是2^x，那么对于n的值直到2 ^（x + 1）-1，迭代是n * x。现在我被卡住了，不知道将这个分类为哪个大哦功能。任何答案/反馈/建议的学习方法/解释欢迎！复杂嵌套循环，利用外环可变逐渐缩小了一半每次迭代

Joker

回答

外环运行 k = n/2，n/4，n/8，...，*。 它完全运行Θ（的log（n））倍 - 这是通过连续分裂降低n/2个至1所需要的，以便通过2

对于?每一个值，而不管该值，内循环运行n次，所以内循环+体运行在Θ（n）时间。

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

复杂嵌套循环，利用外环可变逐渐缩小了一半每次迭代