这段C++代码的时间复杂度是O(n²)还是O(nlogn)？

for (int i = 1; i <= n; i++) {
   for (int j = 1; j <= n; j += i) {
       // some code
   }
}

外层循环显然运行n次。对于内层循环，假设n=8，运行情况如下：

我困惑于内层循环的总复杂度应该是logn还是n，希望能得到解答！

解答 #

这段代码的总时间复杂度既不是O(n)也不是O(logn)，而是O(n log n)。

原因如下：

• 内层循环对每个i的执行次数是⌊n/i⌋（向下取整），总执行次数就是求和式：S(n) = Σ(i=1到n) ⌊n/i⌋
• 这个求和式的渐近行为可以通过近似积分理解：∫₁ⁿ (n/x)dx = n ln n，对应时间复杂度的渐近上界为O(n log n)
• 从实际数值看，n=8时总执行次数是8+4+3+2+2+2+2+1=24，刚好等于n×log₂n（8×3=24）；n越大，这个求和结果越接近n与对数n的乘积量级

简单来说，这段嵌套循环的时间复杂度是线性对数级，也就是O(n log n)。

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