三个嵌套循环的时间复杂度？
三个嵌套循环的时间复杂度？
提问于 2020-10-14 21:03:50
这段代码的时间复杂度是多少？
for(int = n; i > 0; i--){
for(int j = 1; j < n; j*=2){
for(int k = 0; k < j; k++) {
...//constant number C of operations
}
}
}我发现两个内循环产生了O(n*logn)(?)的时间复杂度。再加上外部循环，整个代码(?)的时间复杂度为O(n^2 * logn)。
根据答案，结果应该是O(n^2)，而不是O(n^2 * logn)。
有人能告诉我为什么吗？
回答 1
Stack Overflow用户
发布于 2020-10-15 01:19:56
您说得对，第一个for循环运行O(N)次。让我们来看看里面的两个。
所以看一下j，它将是1,2,4,8,16。n，这意味着内部k循环将运行
1+2+4.+n
时间，或者以另一种方式书写
2^0 + 2^1 +2^2...2^log(N)
您可以查看这个求和，并找到它的O(2^log(n +1))= O(n)。
因此，如果我们将两个内环和外环相乘，我们将得到O(n^2)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/64353916
复制相关文章
相似问题
腾讯云开发者
