algorithm – 依赖嵌套for循环的时间复杂度？

发布时间：2020-12-14 04:56:54 所属栏目：百科来源：网络整理

导读：你能解释一下如何找到时间复杂度吗？ sum=0;for(k=1;k=n;k*=2) for(j=1;j=k;j++) sum++; 所以,我知道外部循环的时间复杂度为O(logn),但由于内部循环的迭代取决于外部循环的值,因此该算法的复杂性不是O(nlogn). 这本书说它是O(n). 我真的不明白它是如何O(n)…

你能解释一下如何找到时间复杂度吗？

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 (geometric series)
= 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)因为nlogn>> n表示n的大值,但它不是渐近紧的.你可以说它是o(nlogn)[小o].

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!