algorithm - 嵌套 for 循环的时间复杂度，内部迭代变量依赖于外部迭代

Question

这是循环结构:

for (int i = 1 ; i < n ; i++) {
    for (int j = 0 ; j < n ; j += i) {
        // do stuff
    }
}

我的猜测是 O(nlogn) 因为它显然不能是 O(n^2) 因为 j 的增量正在增加并且它显然不能是 O(n sqrt(n)) 因为增量不是那么高。但我不知道如何形式化地证明它。

Answer 1

每次内循环的时间复杂度是根据i的值为n/i。因此，总时间为 n + n/2 + n/3 + ... + n/n = n(1+1/2+1/3+...+1/n)。 正如我们所知，1+1/2+1/3+...+1/n 是调和序列并且渐近为 log(n)。因此，该算法的运行时间为 O(nlog(n))。