求内层步长为外层变量2倍的嵌套循环的时间复杂度

先看给出的代码：

for(int i =1; i<=n;i++)
{
    for(int j=i ; j<=n; j+=i*2);
}

内层循环次数计算 #

对于每个外层循环的i，内层循环的j从i开始，每次步长为2i，直到j > n停止。推导内层循环的执行次数：

• j的取值序列为：i, 3i, 5i, ..., (2k-1)i，其中(2k-1)i ≤ n
• 解不等式得：k ≤ (n/i + 1)/2，因此内层循环次数为floor( (n/i + 1)/2 )

总执行次数求和 #

总执行次数是所有i从1到n的内层循环次数之和：
$$\text{总次数} = \sum_{i=1}^n \left\lfloor \frac{n/i + 1}{2} \right\rfloor$$

拆分求和式分析：

1. 当i > n/2时，n/i < 2，代入得(n/i +1)/2 < 1.5，floor结果为1，这部分共有n - floor(n/2) ≈ n/2项，和为O(n)。
2. 当i ≤ n/2时，n/(2i) ≥ 1，此时floor( (n/i +1)/2 )可近似为n/(2i)（忽略floor的微小误差，不影响渐近分析），这部分的和为：
   $$\sum_{i=1}^{\lfloor n/2 \rfloor} \frac{n}{2i} = \frac{n}{2} \sum_{i=1}^{\lfloor n/2 \rfloor} \frac{1}{i}$$
   调和级数$\sum_{i=1}^m \frac{1}{i} ≈ \ln m + \gamma$（$\gamma$为欧拉常数），代入m = floor(n/2)后，这部分和近似为$\frac{n}{2}(\ln(n/2) + \gamma) = O(n \log n)$。

最终时间复杂度 #

将两部分相加，主导项为O(n log n)，因此整个嵌套循环的时间复杂度为O(n log n)。

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