条件语句的时间复杂度 [英] Time complexity with conditional statements

问题描述

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

How does one calculate the time complexity with conditional statements that may or may not lead to higher oder results?

例如：

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条件下的内容被颠倒了怎么办？

And what if the contents in the if-else condition were reversed?

推荐答案

您的代码采用O（n ^ 2）。前两个循环执行O（n ^ 2）个操作。 k循环执行O（n）次操作并被调用n次。得出O（n ^ 2）。代码的总复杂度将为O（n ^ 2）+ O（n ^ 2）= O（n ^ 2）。

Your code takes O(n^2). First two loops take O(n^2) operations. The "k" loop takes O(n) operations and gets called n times. It gives O(n^2). The total complexity of your code will be 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.

这篇关于条件语句的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！