此双循环的时间复杂度 [英] Time Complexity of this double loop
本文介绍了此双循环的时间复杂度的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
这段代码的时间复杂度是多少?
What will be the time complexity of this code?
for(int i = 1 ; i <= b ; ++i )
for(int j = i ; j <= b ; j += i )
推荐答案
您可以将循环扩展为以下内容:
You can expand the loops to something like this:
i = 1 ——> 1,2,3,…,b b
i = 2 ——> 1,3,5,…,b (b/2)
i = 3 ——> 1,4,7,…,b (b/3)
i = 4 ——> 1,5,9,…,b (b/4)
…
i = b ——> 1, b (b/b = 1)
这会扩展为以下形式的总和:
This expands into a sum of the form:
b + b/2 + b/3 + … + b/b = b * (1 + 1/2 + 1/3 + … + 1/b)
您可能认识到第二个因素是谐波系列.然后,使用以下SO答案的结果:找到谐波系列的Big O您可以获得嵌套循环的大哦":
You might recognize the second factor as the Harmonic Series. Then, using the result from the following SO answer: Finding Big O of the Harmonic Series you can get the Big Oh of your nested loops:
O(b * log(b))
这篇关于此双循环的时间复杂度的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文