代码时间复杂度分析疑问：MAX_SIZE增大后count值为何不再变化？

首先看你提供的代码：

int count =0;
for(int i= 1 ; i<=MAX_SIZE ; i*=2){
    for(int j = 1; j<=i*i ; j++){
        if(i%j==0){
            for(int k = 1 ; k<=j ; k++)
                count++;
        }
    }
}
cout<<count<<endl;

你的推导问题所在 #

你错误地将中间循环的复杂度按O(i²)计算，但实际上只有j是i的约数时才会执行内层循环，而i是2的幂次（1,2,4,8,...），它的约数数量非常少——对于i=2^{t，约数只有1,2,4,...,2}t，共t+1个，远小于i²。同时外层循环的i是指数增长的，不能直接用log(n)*n³来推导总复杂度。

count值固定的原因 #

外层循环的i从1开始，每次乘以2，直到i≤MAX_SIZE。对于每个i=2^t，count的增量是i所有约数的和：1+2+4+...+2^t = 2^(t+1)-1。把这些增量累加起来：

• 当i取到32768（2^15）时，累加总和是1+3+7+15+...+65535 = 131054
• 当MAX_SIZE≥32768但小于65536（2^16）时，外层循环不会执行i=65536的情况，所以count固定为131054
• 当MAX_SIZE≥65536时，count会加上65536的约数和131071，变成262125；之后随着MAX_SIZE继续增大，只要超过下一个2的幂次，count还会继续增加

你看到count固定，只是因为MAX_SIZE没有达到下一个2的幂次阈值而已。

正确的时间复杂度分析 #

外层循环执行次数是O(log n)，对应i的取值为1,2,4,...,2^m（其中2m ≤ MAX_SIZE < 2^{(m+1)）。对于每个i=2}t：

• 有效j的数量是t+1个（i的约数个数）
• 每个j对应的内层循环执行j次，总次数为2^(t+1)-1 = O(i)

把所有i的操作次数累加：sum_{t=0}^m 2^t = 2^(m+1)-1，而2^m ≤n，所以这个总和是O(n)。因此这段代码的时间复杂度实际是O(n)。

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