确定Big-o While循环
确定Big-o While循环
提问于 2014-07-16 04:03:15
// n>0
i ← 0
while (i < n)
j ← 0
while (j < power(2,i))
j ← j + 1
done
i ← i + 1
done是总体复杂度O(n(log(N)，因为内部while循环有一个条件where 2^i so 2^02^1^2...=1 2 816 32 64 128...等等。那么对于2^i log(n) > i？
而外部循环看起来简单地是O(n)。
O(n(log(N)的多重双循环复杂度，请确认？提前谢谢。
回答 4
Stack Overflow用户
发布于 2014-07-16 04:14:54
我是O(2^n)
对于外部循环，迭代次数是n，因此对于从0到n-1的每个i值，内部循环都会执行。
每次内循环的迭代次数为2^i，因此整个程序的总迭代次数为：
2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + ... +2^(n-1)这个和等于2^n - 1。因为2^n与1相比太大了，所以我们可以去掉大O符号中的1，从而得到O(2^n)。
Stack Overflow用户
发布于 2014-07-16 08:06:02
通过Sigma表示法使用正式的方法：
Stack Overflow用户
发布于 2014-07-16 04:14:36
看起来像O(2^n)，内部循环是从i=0到i=n-1的和(2^i)，这和2^(i)-1次操作
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/24767155
复制相关文章
相似问题
腾讯云开发者
