嵌套循环的Big O复杂度分析：这段Java代码的时间复杂度是多少？

你对循环执行次数的计算是对的：总执行次数确实是 n/1 + n/2 + n/3 + … + n/(n-1)，但它的复杂度既不是O(n)也不是O(n²)，而是O(n log n)。

具体分析： #

• 提取公共因子n后，总次数可以写成 n * (1 + 1/2 + 1/3 + … + 1/(n-1))，后面这个求和式是调和级数的前n-1项和。
• 调和级数的渐近行为是对数级的：前k项和的增长速度约等于ln(k) + γ（γ是欧拉常数，约0.577），也就是O(log k)。这里k=n-1，所以整体复杂度就是n * O(log n)，即O(n log n)。
• 为什么不是O(n)？因为调和级数的和会随着n增大而持续增长（虽然增长很慢），不是固定常数，所以不能把整个式子简化为n乘以常数；而它的增长速度又远慢于n²，所以也不是O(n²)。

验证例子： #

当n=1000时，调和级数前999项和大约是7，总执行次数约为7000，远小于n²=1000000，同时比n=1000大很多，符合n log n的量级。

附上原代码：

public int sums(int n){
    int sum = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < n/i; j++) {
            sum++;
        }
    }
    return sum;
}

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