嵌套循环的时间复杂度

debugcn 发表于 Dev

辛普森一家

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语句。提前谢谢了！

浪费

您执行外循环log(n)时间，因为每次您将i的值翻倍

然后执行内部循环n次数，最后一次内部循环执行一次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最内层循环的时间添加到第二个内层循环的运行时间中最内部的循环，然后将其与执行最重要的内部循环的总时间相乘

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。