java - 嵌套循环的时间复杂度

Question

for(int i = 1; i < n; i = i ∗ 2){
     for(int j = 0; j < n; j++){
         if(i == j){
            for(int k = 0; k < n; k++){
               // Do something elementary
            }
         }else{
            // Do another elementary thing
         }
     }
 }

我正在做一些练习，有人可以帮我算出上述算法的 θ 吗？我知道如果只是两个外部嵌套循环，时间复杂度应该是 θ(nlogn)。但我不知道如何处理 if-else 语句。提前谢谢了!

Answer 1

执行外循环 log(n) 次，因为每次都会将 i 的值加倍

然后你执行内部循环n次，最后一个内部循环inf你执行一次的if语句(如果i == j成立)n 次，整个内部循环每次都需要n + n步。

这为您提供了 O(2n log(n)) 的上限，并且由于常量不会改变渐近复杂度，因此运行时的界限为 O(n log(n))

for(int i = 1; i < n; i = i ∗ 2){                    ----------
 for(int j = 0; j < n; j++){            ----------             |
     if(i == j){                                  |            |
        for(int k = 0; k < n; k++){     ----      |            |
           // Do something elementary       | (n  | + n )      | * log(n)
        }                               ----      |            |
     }else{                                       |            |
        // Do another elementary thing            |            |
     }                                  ----------             |
 }                                                             |
}                                                              |
                                                   ------------

请注意，最内层循环每秒仅执行一次(!)，并且由于第二个最内层循环被执行 log n 次(有 n 步骤)我们必须将最内层循环的 n 次添加到第二个最内层循环的运行时间，然后将其乘以执行第二个最内层循环的总时间