algorithm - 三个嵌套循环的时间复杂度？

Question

代码的时间复杂度是多少

for(int i=0; i<n;i++){
    for(int j =0; j<n; j++){
        for(int k=1; k<n; k*=2){
            count++;
        }
    }  
}

前 2 个循环创建一个 O(n^2) 对吗？

在第三个循环中“int k=1”执行了1次，

那k呢

k*=2

和计数++

换句话说，第三个循环的时间复杂度是多少？

Answer 1

内部循环是 O(log n)，因为“递增”步骤实际上是乘法。

这意味着整个算法是O(n^2 log n)。

count++; 在常数时间内执行，因此它对大 O 分析没有任何贡献。