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

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)，因为 "increment" 步骤实际上是一个乘法。

也就是说整个算法是O(n^2 log n).

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

Answer 2

如果你想彻底分析你的算法，你可以使用Sigma符号来分析count++;执行的次数

因此，您的算法在 O(n^2 · log n) 中运行。

注意：等式 (*) 适用于 n 的所有值，这些值不是 2 (n%2 != 0) 的倍数。在 n 是 2 (n%2 = 0) 的倍数的情况下，只需删除总和和后续表达式中的 floor function等于 (*) 以上。

现在，根据上面的内容，我们意识到 T(n) 的表达式恰好在上面的小于或等于符号 (≤) 之前指定，将产生 [=24] 的精确值=] 在循环之后（假定 count=0 在循环之前），而不隐含地需要执行嵌套循环。

T(n) = n^2*(1 + floor(log(n)/log(2))), if n%2 != 0,
       n^2*(1 + log(n)/log(2)),        if n%2  = 0.

如果您的算法只是计算一些东西，这会很有用；与其显式地执行循环来执行这样一个乏味的（并且，对于 n 的大值，缓慢的）计数任务，您可以推导出自己的计数公式，就像上面一样，并在您的程序中使用相反。

我们可以验证为这种情况导出的公式是否正确计算了实际的迭代次数：

//        count                 count
// n      (after triple loop)   (by T(n) formula)
// ----   -------------------   -----------------
// 10     400                   400
// 100    70 000                70 000
// 1000   10 000 000            10 000 000

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

Time complexity of three nested loops?

algorithm

complexity-theory

big-o

time-complexity