조건문을 사용한 시간 복잡도

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을 분석하는 경우 하나의 분기 또는 다른 분기를 입력 할 확률을 계산하고 각 복잡성에 해당 경로를 사용할 확률을 곱해야합니다.

분기를 변경하는 경우 확률 계수를 전환하면됩니다.