Wie ermittle ich die Laufzeit dieses Algorithmus?

-1

Ich habe einen Sortieralgorithmus implementiert, und ich kann nicht herausfinden, wie lange es dauern würde, in schlechtesten, besten oder durchschnittlichen Fällen. Wie kann ich das angehen?Wie ermittle ich die Laufzeit dieses Algorithmus?

Eine visuelle Darstellung hier: https://plus.google.com/117480037533147789168/posts/FpgbKsyNLSL

public int[] shortingSort(int[]unsortedArray){ 
    int k = 1; 
    for (int i = 0; i<Math.floor(unsortedArray.length/2); i++){ 

     while(k != unsortedArray.length-1-i){      

       if(k!= i && unsortedArray[i]>unsortedArray[k]){ 
        int sub = 0; 
        sub = unsortedArray[i]; 
        unsortedArray[i] = unsortedArray[k]; 
        unsortedArray[k] = sub;    
       } 

       if(k!= unsortedArray.length-1-i && 
         unsortedArray[unsortedArray.length-1-i] < unsortedArray[k]){ 

        int sub = 0; 
        sub = unsortedArray[unsortedArray.length-1-i]; 
        unsortedArray[unsortedArray.length-1-i] = unsortedArray[k]; 
        unsortedArray[k] = sub;    
       } 
       k++; 
     } 
     if(k == unsortedArray.length-1-i){ 
      k = 1 + i; 
     } 
    } 
return unsortedArray; 
}

Quelle

2017-07-08 Merlin Santowski

sieht aus wie ein 'n^2' Zeit mir Komplexität Algorithmus. Die äußere Schleife läuft in "n/2", während die innere Schleife in "n/2", "n/2 - 1", "n/2 - 2" läuft ... – Turing85

Könnten Sie mir erklären, warum der innere? ist n/2, n/2 - 1, n/2 - 2 ... und so weiter? –

Oh Entschuldigung, es läuft in 'n/2',' n/2 - 2', 'n/2 - 4',' n/2 - 6' ... Für jede Iteration der äußeren Schleife, 'i' wird um eins erhöht. Die innere Schleife läuft, während 'k! = N - 1 - i'. Die Variable "k" wird nur um "1" inkrementiert, somit hat "k" den Wert "n - 1 - i" nach der inneren Schleife (macht das "if" überflüssig), und "k" wird auf "i + 1" gesetzt . Daher macht die nächste innere Schleife zwei Iterationen weniger als die aktuelle Iteration. Dies führt zu den Summanden: "n/2 + (n/2 - 2) + (n/2 - 4) + (n/2 - 6) + ... + 2", was zu einem "n^2" führt Zeitkomplexitätsalgorithmus. – Turing85

Lässt die Länge Ihres unsortedArray als N markieren.
Ihre äußere Schleife:

for (int i = 0; i<Math.floor(unsortedArray.length/2); i++)

Läuft N/2 Zeiten wird i nicht innerhalb der Schleife verändert wird.
In Ihrer inneren Schleife:

while(k != unsortedArray.length-1-i)

k ist Schritte einmal (k++) innerhalb der Schleife, und gleich nach den Schlaufenenden zu sein, wird es die if Anweisung, nachdem es ein (es wird immer geben, weil es für prüft die gleiche Bedingung, die die while Schleife gestoppt hat). Und es aktualisiert k zu i+1 sein. Welches wird 1, 2, 3, 4, 5, ..., N/2 sein.
Dies bedeutet, dass die innere Schleife bei jeder Iteration Ihrer äußeren Schleife 1 mal weniger ausgeführt wird.

Geben SUM(N/2, N/2-1, N/2-2, ... , 1) = O((N/2)^2) = O(N^2)

Quelle

2017-07-08 14:11:00

Wie ermittle ich die Laufzeit dieses Algorithmus?

Antwort

Verwandte Themen