为何该C嵌套循环代码时间复杂度为O(n²)而非O(n³)？

待分析代码 #

void f(int n)
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n * n / i; j += i)
            printf("*");
}

核心疑问 #

最初推导得到时间复杂度为O(n³)，但标准答案为O(n²)，对推导逻辑存在疑问。

你得出O(n³)的核心误区是：忽略了内层循环的步长为i而非1，同时错误地将外层循环次数直接乘以i取最小值时的内层最大循环次数，没有对所有i对应的内层循环次数做累加计算。
实际推导按以下步骤进行：

1. 计算固定i值下的内层循环次数
   对于确定的外层循环变量i，内层循环j的上界为n²/i，步长为i，因此单轮内层循环的迭代次数约为 (n²/i) / i = n²/i²（整数除法带来的常数误差不影响复杂度计算）。
2. 累加所有外层轮次的操作数得到总执行次数
   总操作数T(n)是i从1到n的内层循环次数之和：
   T(n) = Σ(i=1到n) n²/i² = n² * Σ(i=1到n) 1/i²
3. 利用级数性质化简求和项
   当p>1时，p级数Σ(i=1到∞)1/i^p收敛为常数，此处p=2，无穷项和为π²/6≈1.64，也就是说无论n取多大，Σ(i=1到n)1/i²的值永远小于这个固定常数，属于*O(1)*量级。
4. 得到最终复杂度
   代入总执行数公式可得 T(n) = n² * O(1) = O(n²)，和标准答案一致。

如果内层循环步长为1，那么单轮内层循环次数为n²/i，总次数为n²*Σ(i=1到n)1/i = n² * logn，复杂度为O(n²logn)，依然到不了O(n³)；你之前的O(n³)结论是错误假设内层每轮都执行n²次，但实际上只有i=1时内层执行n²次，随着i增大，内层循环次数以1/i²的速度快速下降，累加总和不会超过2n²，远达不到n³的量级。

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