谁能解释一下这个算法的时间复杂度是多少?
for (i = 1; i <= n; i++){
for(j = 1; j <= n; j += i) { // note: not j++
printf("Iteration %d : %d\n", i, j);
}
}
The printf
在内循环中称为exactly 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
but is < 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
.
后一个因子是无穷大的第一个加数是谐波级数 https://en.wikipedia.org/wiki/Harmonic_series_(mathematics),这有所不同。第一个的总和k
已知维基百科页面中的术语是有界的:
意思就是1 + 1/2 + 1/3 + 1/4 ... 1/n
is Ө(ln n) = Ө(log n)
;我们可以对出现的次数给出严格的限制printf
叫做 (c(n)
: n log n <= c(n) < n log n + 2n
. Since n log n
增长速度快于2n
,我们可以只保留前者,并注意到两个边界都属于Ө(n log n)
因此c(n)
属于Ө(n log n)
还有(Ө(F)
意味着该函数既是Ω(F)
and O(F)
).
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)