Сложность времени с условными операциями

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

А что, если содержимое в если-то еще условия были отменены?

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, то возьмите наихудшую сложность обеих ветвей. Если вы анализируете average-case complexity, вам нужно рассчитать вероятность входа в одну ветвь или другую и умножить каждую сложность на вероятность прохождения этого пути.

Если вы меняете ветви, просто переключите коэффициенты вероятности.