计算嵌套循环的复杂度

Question

我知道每个 for 循环都是 O(log₂n)，但我不确定其中 3 个循环会产生什么？ O（3⋅log2n）？谢谢大家。

for (int i = n; i > 0; i = i / 2) {
    for (int j = n; j > 0; j = j / 2) {
        for (int k = n; k > 0; k = k / 2) {
            count++;
        }
    }
}

Answer 1

正如你所说，它自己的每个循环都有时间复杂度Θ(log₂n)。

由于循环不相互依赖，即变量i、j和k相互之间没有影响，三个嵌套循环的复杂度可以简单地相乘就得到 Θ((log₂n)⋅(log₂n)⋅(log₂n)) = Θ((log₂n)³)，也写成 Θ(log₂³n)。这意味着它也在 O(log₂³n).

注意：您可以不将log₂³n简化为3⋅log₂n，因为log₂³n不等于log₂n³。