algorithm - 计算“时间复杂度”

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仍在执行。

条件检查 , i<n1, j<n2, 和 , 和 , 和等增量k<n3操作仍然发生。i++j++k++

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

如果您没有在if条件下执行恒定时间操作：

那么时间复杂度将取决于for循环中执行的操作。