条件语句的时间复杂度

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-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

这取决于您执行的分析类型。如果您正在分析 worst-case complexity, then take the worst complexity of both branches. If you're analysing average-case complexity，则需要计算进入一个分支或另一个分支的概率，并将每个复杂度乘以采用该路径的概率。

如果改变分支，只需要改变概率系数即可。

条件语句的时间复杂度

Time complexity with conditional statements

code-analysis