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);   
    }
}

标签： ctime-complexitybig-o

Answer 1

printf内部循环中的in 被准确地 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。

后一个因素是无穷大的第一个加数是发散的谐波级数。k已知 Wikipedia 页面中第一个术语的总和是有界的：

这意味着这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)）。