有条件语句的时间复杂性

Question

一个人如何通过可能导致或可能不会导致更高的ODER结果计算时间复杂性？

例如：

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-ELSE条件下的内容逆转了怎么办？

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

取决于您正在执行的分析。如果您正在分析最坏情况的复杂性，则应采用两个分支的最差复杂性。如果您要分析平均案例复杂性，则需要计算输入一个分支或另一个分支的概率，并通过采用该路径的概率将每个复杂性乘以。

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