依赖嵌套的for循环的时间复杂度? [英] Time complexity for dependant nested for loop?

问题描述

您能解释一下如何找到时间复杂度吗?

sum=0;
for(k=1;k<=n;k*=2)
  for(j=1;j<=k;j++)
     sum++;

因此，我知道外循环的时间复杂度为O(logn)，但是由于内循环的迭代取决于外循环的值，因此该算法的复杂度不是O(nlogn).

这本书说它是O(n).

我真的不明白它是O(n)...有人可以解释一下吗... 如果您能详细介绍一下:D

数学解决方案可以帮助我更好地理解...

解决方案

外循环执行了log(Base2)n次，所以它是O(log(Base2)n).

内部循环对于外部循环的每次迭代执行k次.现在，在外部循环的每次迭代中，k递增为k * 2.

所以内循环迭代总数= 1 + 2 + 4 + 8 + ... + 2 ^(log(Base2)n)
= 2 ^ 0 + 2 ^ 1 + 2 ^ 2 + ... + 2 ^ log(Base2)n (几何级数)
= 2 ^((log(base2)n + 1)-1/(2-1)
= 2n-1.
= O(n)
所以内循环是O(n) 因此，总时间复杂度= O(n)，因为O(n + log(base2)n)= O(n).

更新:它也是O(nlogn)，因为对于n的大值，nlogn >> n，但是它不是渐近紧的.您可以说它是o(nlogn)[Small o].

Can you explain me how to find time complexity for this?

sum=0;
for(k=1;k<=n;k*=2)
  for(j=1;j<=k;j++)
     sum++;

So, i know the outer loop has time complexity of O(logn), but since the iterations of the inner loop depends on the value of the outer loop, the complexity of this algorithm is not O(nlogn).

The book says it is O(n).

I really dont understand how it is O(n)...Can someone please explain it... I'll be really grateful if u could go into the details btw :D

A mathematical solution would help me understand better...

解决方案

The outer loop executed log(Base2)n times.so it is O(log(Base2)n).

the inner loop executed k times for each iteration of the outer loop.now in each iteration of the outer loop, k gets incremented to k*2.

so total number of inner loop iterations=1+2+4+8+...+2^(log(Base2)n)
=2^0+2^1+2^2+...+2^log(Base2)n (geometric series)
=2^((log(base2)n+1)-1/(2-1)
=2n-1.
=O(n)
so the inner loop is O(n). So total time complexity=O(n), as O(n+log(base2)n)=O(n).

UPDATE:It is also O(nlogn) because nlogn>>n for large value of n , but it is not asymptotically tight. you can say it is o(nlogn)[Small o] .

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