两段嵌套循环代码的时间复杂度T(n)计算及解析请求

让咱们一步步拆解这两段代码的时间复杂度，把逻辑理得明明白白：

先把代码贴出来方便参考：

for(int i=2;i<=n;i++) {
    for(int j=0;j<=n;) {
        std::cout<<i<<" "<<j<<"\n";
        j=j+(n/4);
    }
}

外层循环分析 #

外层循环从i=2跑到i=n，总共执行的次数是n-1次——这个数和n是线性关系，忽略常数项的话可以看成O(n)量级。

内层循环分析 #

题目里说n能被4整除，那n/4是整数。内层循环的j从0开始，每次跳n/4，直到j>n时退出。咱们数一下执行次数：

• 第一次：j=0 → 执行输出，然后j变成n/4
• 第二次：j=n/4 → 执行输出，j变成2n/4
• 第三次：j=2n/4 → 执行输出，j变成3n/4
• 第四次：j=3n/4 → 执行输出，j变成4n/4 = n
• 第五次：j=n → 执行输出，j变成n + n/4 = 5n/4（这时候j>n，循环结束）

不管n是多大的4的倍数，内层循环固定执行5次，属于常数时间O(1)。

总时间复杂度 #

总操作次数是外层循环次数 × 内层循环次数，也就是(n-1)*5。渐进时间复杂度忽略常数和低阶项，所以T(n) = O(n)，精确表达式是T(n)=5n-5，属于θ(n)范畴。

同样先贴代码：

for (int i=1; i<=n; i++) {
    j = n;
    while(j>=1) {
        <body of the while loop> //Needs θ(1)
        j=⌊j/2⌋; // ⌊⌋=>Floor function
    }
}

题目说明n是2的幂，也就是n=2^k（k是正整数）。

外层循环分析 #

外层循环从i=1到i=n，总共执行n次，这个没什么疑问，是O(n)量级。

内层while循环分析 #

每次外层循环里，j初始值都是n=2^k，然后每次取floor除以2，直到j<1为止。咱们数一下执行次数：

• j的取值依次是：2^k → 2^(k-1) → 2^(k-2) → ... → 2^0=1 → 下一次除以2得到0，退出循环
• 总共执行的次数是k+1次，而因为n=2^k，所以k=log₂n，也就是内层循环次数是log₂n +1，渐进量级是O(log n)。

总时间复杂度 #

总操作次数是外层循环次数 × 内层循环次数，也就是n*(log₂n +1)。忽略常数项后，渐进时间复杂度T(n)=O(n log n)，精确表达式是T(n)=n log₂n +n，属于θ(n log n)范畴。

内容的提问来源于stack exchange，提问作者user9043303