计算嵌套for循环的复杂性 [英] Calculate the complexity of a nested for loop

问题描述

我想计算这个嵌套for循环的复杂性：
$ b $ pre $ s = 0; （j = 1; j <= i; j * = 2）
s ++;对于（i = 1;i≤n; i * = 2）
，


我用什么策略来找到这段代码的大O复杂性？

解决方案

外层循环遍历1,2,4,8，... n lg n ）步骤，因为您只能加倍一次O（lg n ）次，直到按 n 。

内层循环也是一样的。它只能到达 i ，但是在外循环的最后迭代中， i 达到了最大值，这又是 n ，所以也就是O（lg n ）。

把它们放在一起给出一个O（（lg n ）） ²），通常缩写为O（lg² n ）。

I want to calculate the complexity of this nested for loop:

s = 0;
for(i=1; i<=n; i*=2)
   for(j=1; j<=i; j*=2)
      s++;

What strategy do I use to find the Big O complexity of this piece of code?

解决方案

The outer loop marches through 1, 2, 4, 8, ... n, which takes O(lg n) steps because you can only double one O(lg n) times until you hit n.

The inner loop does the same. It only goes up to i, but in the final iteration of the outer loop, i reaches its maximum value which is again n, so that's also O(lg n).

Putting this together gives an upper bound of O((lg n)²), which is commonly abbreviated O(lg² n).

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