Bestimmung der Wachstumsfunktion und Big O

Question

Bevor jemand fragt, ja das war eine vorherige Testfrage, die ich falsch verstanden und wusste, dass ich falsch lag, weil ich ehrlich gesagt nicht nur Wachstumsfunktionen und Big O verstehe. Ich habe die technische Definition gelesen, Ich weiß, was sie sind, aber nicht, wie sie berechnet werden. Mein Lehrbuch gibt Beispiele aus realen Situationen, aber ich finde es immer noch schwer, Code zu interpretieren. Wenn jemand mir ihren Gedankengang darüber erzählen kann, wie sie diese bestimmen, würde das ernsthaft helfen. (d. h. dieser Codeabschnitt sagt mir, dass ich n mit x, usw. multiplizieren soll).

public static int sort(int lowI, int highI, int nums[]) { 

     int i = lowI; 
     int j = highI; 

     int pivot = nums[lowI +(highI-lowI)/2]; 

     int counter = 0; 

     while (i <= j) { 
      while (nums[i] < pivot) { 
       i++; 
       counter++; 
      } 
      while (nums[j] > pivot) { 
       j--; 
       counter++; 
      } 

      count++; 
      if (i <= j) { 
       NumSwap(i, j, nums); //saves i to temp and makes i = j, j = temp 
       i++; 
       j--; 
      } 
     } 

     if(lowI< j) 
     {  
      return counter + sort(lowI, j, nums); 
     }  
     if(i < highI) 
     {  
      return counter + sort(i, highI, nums); 
     } 

     return counter; 

    } 

Answer 1

Es könnte helfen, für Sie some explanations of Big-O zu lesen. Ich denke an Big-O, da die Anzahl der "Basisoperationen", die als "Eingabegröße" berechnet werden, zunimmt. Für Sortieralgorithmen bedeutet "Basisoperationen" normalerweise Vergleiche (oder in Ihrem Fall counter Inkremente), und die "Eingabegröße" ist die Größe der zu sortierenden Liste.

Wenn ich zur Laufzeit analysiere, werde ich durch beginnen, den Code in Abschnitte mental zu teilen. Ich ignoriere einmalige Zeilen (wie int i = lowI;), weil sie nur einmal ausgeführt werden, und Big-O kümmert sich nicht um Konstanten (obwohl in Ihrem Fall int i = lowI; einmal mit jeder Rekursion läuft, so dass es nicht nur ausgeführt wird einmal insgesamt).

Zum Beispiel würde ich Ihren Code mental in drei Teile teilen, um zu analysieren: Es gibt die Haupt-while-Schleife while (i <= j), die zwei while-Schleifen innerhalb davon und die zwei rekursiven Aufrufe am Ende. Für wie viele Iterationen werden diese Schleifen ausgeführt, abhängig von den Werten i und j? Wie oft wird die Funktion abhängig von der Größe der Liste wiederholt?

Wenn ich Probleme habe, über all diese verschiedenen Teile auf einmal nachzudenken, werde ich sie isolieren. Wie lange wird beispielsweise eine der inneren for-Schleifen ausgeführt, abhängig von den Werten i und j? Wie lange läuft dann die äußere while-Schleife?

Sobald ich über die Laufzeit von jedem Teil gedacht habe, werde ich bringen sie wieder zusammen. In diesem Stadium ist es wichtig, über die Beziehungen zwischen den verschiedenen Teilen nachzudenken. "Verschachtelte" Beziehungen (d. H. Der verschachtelte Block wiederholt sich jedes Mal, wenn das äußere Objekt einmal eine Schleife ausführt), bedeutet normalerweise, dass die Laufzeiten multipliziert werden. Da die inneren while-Schleifen beispielsweise innerhalb der äußeren while-Schleife verschachtelt sind, beträgt die Gesamtzahl der Iterationen (inner run time + other inner) * outer. Es scheint auch, dass die Gesamtlaufzeit in etwa so aussehen würde - ((inner + other inner) * outer) * recursions - auch.