求带if判断的三层嵌套for循环的时间复杂度大O表示

开发者阿泽

2026-9-26

你的推导思路和结果都不正确，正确的时间复杂度大O表示为O(n²)，以下是详细讲解：

错误点梳理

你犯了嵌套循环复杂度计算的常见误区：直接将每一层的独立最坏上限相乘，忽略了两个核心影响因素：

中间层循环的上限i*i是随外层的i动态变化的，不是固定的n²
最内层循环只有j是i的约数时才会触发，不是每次中间层迭代都会执行

逐层计算逻辑

第一层循环：i的迭代

for(int i =1 ; i <=n ; i*=2)

i的取值为1、2、4、8……直到不超过n，总迭代次数为floor(log₂n) + 1，复杂度为O(log n)，这部分你的判断是正确的。

第二层循环+if判断的总开销

for(int j =1; j<= i * i; j++)
   if (i % j == 0)

这里每一次j的迭代都会执行一次取余判断，这部分开销必须计入总复杂度，不能忽略。我们直接计算所有外层i对应的第二层总迭代次数：
i是2的幂，设i=2^m，m从0到log₂n，那么i²=4^m，所有i的i²之和是公比为4的等比数列：
总次数 = 1² + 2² + 4² + 8² + … + (2^t)² （其中2^t ≤n <2^{t+1}）
等比数列求和结果为(4^{t+1} -1)/3，代入2^t ≤n，可得4^{t+1}=4*(2^t)² ≤4n²，因此这部分的总开销为O(n²)。

最内层循环的总开销

for(int k = 1; k<=j; k++) 
   y=y*x;

只有当j是i的约数时才会执行该层循环，对于每个i，所有符合条件的j的j值之和就是i的正约数和σ(i)。
因为i是2的幂，它的约数只有1、2、4……i，约数和为2i-1，所以所有i的约数和总和为：
Σ(2i-1) （i取所有<=n的2的幂）= 2*(2^{t+1}-1) - (t+1) ≤4n - log n，复杂度为O(n)，远小于第二层的O(n²)，不属于主导项。