c - 时间复杂度 嵌套循环 内循环+外循环

Question

谁能解释一下这个算法的时间复杂度是多少？

for (i = 1; i <= n; i++){
    for(j = 1; j <= n; j += i) {   // note: not j++
        printf("Iteration %d : %d\n", i, j);   
    }
}

Answer 1

printf在内部循环中被称为完全 ceil(n) + ceil(n/2) + ceil(n/3) + ... ceil(n/n)次。摆脱ceil ，我们知道 ceil(y/n)以 y/n + 1 为界, 所以我们知道执行次数是>= n + n/2 + n/3 ... n/n但是是 < n + 1 + n/2 + 1 + n/3 + 1 + n/4 + 1... + n/n + 1 .前者可以因式分解为 n(1 + 1/2 + 1/3 + 1/4 ... 1/n)后者可以重构为 n(1 + 1/2 + 1/3 + 1/4 ... 1/n) + n .

后一个因子是无穷大的第一个加数是 the harmonic series , 发散。第一个的总和k来自维基百科页面的术语已知是有界的:

这意味着1 + 1/2 + 1/3 + 1/4 ... 1/n是Ө(ln n) = Ө(log n) ;我们可以严格限制 printf 出现的次数被称为 ( c(n) : n log n <= c(n) < n log n + 2n 。由于 n log n 比 2n 增长得更快，我们可以只保留前者并注意到两个边界都属于 Ө(n log n) 因此 c(n) 也属于 Ө(n log n) ( Ө(F) 表示该函数既是 Ω(F) 又是 O(F) )。