3个嵌套循环的大O
提问于 2013-01-24 21:02:32
另一个大O符号question...What是下面代码的大O：
for (int i = n; i > 0; i = i / 2){
for (int j = 0; j < n; j++){
for (int k = 0; k < n; k++){
count++;
}
}
}我的想法是:分解一下，我认为外部循环是O(log2(n))，那么每个内部循环都是O(n)，这会导致O(n^2 * log2(n))问题#1，对吗？
问题#2:当组合嵌套循环时，它总是像每个循环的大O一样简单吗？
回答 2
Stack Overflow用户
发布于 2013-01-24 21:05:24
- 是的，这是正确的:外部循环是
logN，另外两个是N，对于所有的简单情况，是的。在更复杂的情况下，当循环索引从其他索引指示的数字开始时，计算会更加复杂。
Stack Overflow用户
发布于 2014-04-15 12:51:02
你可以正式地使用Sigma符号，忠实地模仿你的循环：
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/14510701
复制
腾讯云开发者
