Zeitkomplexität mit bedingten Anweisungen

Question

Wie berechnet man die Zeitkomplexität mit bedingten Anweisungen, die zu höheren Ergebnissen führen können oder nicht?

Zum Beispiel:

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

Und was, wenn der Inhalt in dem if-else Zustand rückgängig gemacht wurde?

Answer 1

Ihr Code benötigt O (n^2). Die ersten beiden Schleifen nehmen O (n^2) -Operationen. Die "k" -Schleife benötigt O (n) -Operationen und wird n-mal aufgerufen. Es gibt O (n^2). Die Gesamtkomplexität Ihres Codes ist O (n^2) + O (n^2) = O (n^2).

Ein weiterer Versuch:

- 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

Das von der Art der Analyse ab, die Sie durchführen. Wenn Sie worst-case complexity analysieren, nehmen Sie die ungünstigste Komplexität beider Zweige. Wenn Sie average-case complexity analysieren, müssen Sie die Wahrscheinlichkeit berechnen, in die eine oder andere Verzweigung einzutreten, und jede Komplexität mit der Wahrscheinlichkeit multiplizieren, mit der dieser Pfad genommen wird.

Wenn Sie die Zweige ändern, wechseln Sie einfach die Wahrscheinlichkeitskoeffizienten.