条件语句的时间复杂性

Question

如何用条件语句计算时间复杂度，这些语句可能会或不会导致更高的结果？

例如：

for(int i = 0; i < n; i++){  
   //an elementary operation   
   for(int j = 0; j < n; j++){
       //another elementary operation  
       if (i == j){  
           for(int k = 0; k < n; k++){
               //yet another elementary operation
           }
       } else {
           //elementary operation
       }
   }
}

如果if -条件下的内容被逆转了呢？

Answer 1

您的代码取O(n^2)。前两个循环采用O(n^2)运算。"k“循环接受O(n)操作，并被调用n次。给出了O(n^2)。代码的总复杂度为O(n^2) + O(n^2) = O(n^2)。

另一次尝试：

 - First 'i' loop runs n times.
 - Second 'j' loop runs n times. For each of is and js (there are n^2 combinations):
     - if i == j make n combinations. There are n possibilities that i==j, 
      so this part of code runs O(n^2).
     - if it's not, it makes elementary operation. There are n^2 - n combinations like that
       so it will take O(n^2) time.
 - The above proves, that this code will take O(n) operations.

Answer 2

这取决于您正在执行的分析类型。如果您正在分析最坏情况复杂性，那么请考虑这两个分支中最复杂的部分。如果您正在分析平均情况复杂性，您需要计算进入一个分支或另一个分支的概率，并将每个复杂性乘以走这条路径的概率。

如果您更改了分支，只需切换概率系数。