嵌套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)).