咨询嵌套循环代码的时间复杂度：是否为O(n²)？

你的答案O(n²)不正确，这段代码的时间复杂度实际是O(n log n)，具体分析如下：

先看代码实现：

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

外层循环执行n次，但内层循环的迭代次数随i的取值变化：

• 当i=1时，j每次递增1，内层循环执行约n次（准确为n-1次，大O分析中可近似为n）
• 当i=2时，j每次递增2，内层循环执行约n/2次
• 当i=3时，内层循环执行约n/3次
• ...
• 当i=n时，j仅能取1（1 + n >=n），内层循环执行1次

总操作次数是所有内层循环次数的总和，即：
$n \times (1 + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{n})$

括号内的部分是调和级数，它的渐近增长速度与$\ln(n)$成正比（加上一个常数项，大O分析中可忽略），因此整体时间复杂度为$O(n \log n)$。

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