时间复杂度嵌套循环内循环+外循环 [英] Time Complexity Nested Loop Inner Loop + Outer Loop

问题描述

任何人都可以解释该算法的时间复杂度吗?

Can anyone explain what the time complexity is for this algorithm?

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

推荐答案

内部循环中的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 printf in the inner loop is called exactly ceil(n) + ceil(n/2) + ceil(n/3) + ... ceil(n/n) times. To get rid of ceil, we know that ceil(y/n) is bounded above by y/n + 1, so we know that the number of executions is >= n + n/2 + n/3 ... n/n but is < n + 1 + n/2 + 1 + n/3 + 1 + n/4 + 1... + n/n + 1. The former can be factored to n(1 + 1/2 + 1/3 + 1/4 ... 1/n) and the latter can be refactored into to n(1 + 1/2 + 1/3 + 1/4 ... 1/n) + n.

后一个因素是无穷大的第一个加法子是谐波序列，这有所不同.已知Wikipedia页面中的前k个术语的总和是有界的:

The latter factor is of the first addend to infinity is the the harmonic series, which diverges. The sum of the first k terms from the Wikipedia page is known to be bounded:

表示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)).

which means that 1 + 1/2 + 1/3 + 1/4 ... 1/n is Ө(ln n) = Ө(log n); we can give strict bounds for the number of times that printf is called (c(n): n log n <= c(n) < n log n + 2n. Since n log n grows faster than 2n, we can keep only the former and notice that both bounds belong to Ө(n log n) and hence c(n) belongs to Ө(n log n) as well (Ө(F) means that the function is both Ω(F) and O(F)).

这篇关于时间复杂度嵌套循环内循环+外循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！