计算 "Time Complexity"

Question

希望你一切顺利，

我正在计算我的算法的 时间复杂度 ，它有三个嵌套的 for，但我通过在最新的 if 中放置了一个技巧for 喜欢：

for (i=0 ; i<n1 ; i++){
    for (j=0 ; j<n2 ; j++){
        for (k=0 ; k<n3 ; k++){
            if (A[i][j][k] == true){
               ...
            }
        }
     }
 }

所以，如果 A[i][j][k] 是 false 那么它将被跳过并且不会使用计算时间。

我的问题是：我们是否跳过了某些部分，算法的复杂度再次是 O(n1*n2*n3)，当 n1=n2=n3=n 时，是 O(n^3)?

感谢您的宝贵时间。

Answer 1

如果在if条件下进行常数时间运算：

复杂度仍然为 O(n^3)，因为 条件 和 for 循环的 afterthought 部分仍在执行。

条件检查，即i<n1、j<n2、k<n3和i++、j++、[=]等自增操作17=] 仍然发生。

因此，不会跳过这些计算。

如果在if条件下不进行常数时间运算：

然后时间复杂度将取决于在 for 循环中执行的操作。