Laufzeit Analyse von Algorithmen

Hallo zusammen,

das Informatik-Forum geht in den Archivmodus, genaue Informationen kann man der entsprechenden Ankündigung entnehmen. Als Dankeschön für die Treue bekommt man von uns einen Gutscheincode (informatikforum30) womit man bei netzliving.de 30% auf das erste Jahr sparen kann. (Genaue Infos sind ebenfalls in der Ankündigung)

Vielen Dank für die Treue und das Verständnis!

    Hallo,



    ich möchte bei folgendem Algorithmus eine Laufzeit - Analyse für den worst-case durchführen!



    Code
    [/color] [color=black]void xyzSort(unsigned long a[], unsigned long laenge) [/color] [color=black]{[/color] [color=black]l = 0; //Zeile 1[/color] [color=black]r = laenge -1; //Zeile 2[/color] [color=black]for(i = r; i>=l+1; i--) //Zeile 3[/color] [color=black]{[/color] [color=black]	 for(j=l;j<=i-1;j++) //Zeile 4[/color] [color=black]	 {[/color] [color=black]		 if(a[j] >= a[i]) //Zeile 5[/color] [color=black]		 {[/color] [color=black]			temp = a[i]; //Zeile 6[/color] [color=black]			a[i] = a[j]; //Zeile 7[/color] [color=black]			a[j] = temp; //Zeile 8[/color] [color=black]		 }[/color] [color=black]	 }[/color] [color=black]	}[/color] [color=black]}[/color] [color=black]

    [/color]

    kurze Eläuterung des Sortierprinzips dieses Algorithmus(nach meiner Interpretation):

    Von übergebenem Array werden letztes und erstes Element miteinander verglichen. Falls das erste größer ist, werden beide vertauscht. Als nächstes wird das zweite Element mit dem letzten verglichen und gegebenfalls vertauscht, usw.... Die Sortierung erfolgt aufsteigend!



    Zur Laufzeitanalyse: (Annahme: eine Zeiteinheit für jede Anweisung)
    Laufzeit immer durch zwei || abgetrennt:



    Zeile: Zeiteinheit:

    (1) Initialisierung l = 0 ||1

    (2) Initialisierung r = laenge-1 ||1

    (3) Initialisierung i=r ||1

    letzter Vergleich(in Schleife) i >= l+1 ||1

    -------------------------------------------------------------------------

    Dekrementierung i-- ||1 (r - mal)

    Vergleich i>= l+1 ||1

    (4) Initialisierung j = l ||1

    letzter Vergleich j <=i-1 ||1

    -------------------------------------------------------------------------

    Inkrementierung j++ ||1 (r - mal)

    Vergleich j <=i-1 ||1

    (5) Vergleich a[j] >= a[i] ||1

    (6) Zuweisung(worst case) temp = a[i] ||1

    (7) Zuweisung(worst case) a[i] = a[j] ||1

    (8) Zuweisung(worst case) a[j] = temp ||1

    -------------------------------------------------------------------------

    6 * r + 4 * r + 2





    Nach meiner Berechnung sollte die Laufzeit O(r²) sein! Die beider for - Schleifen haben jeweils O(r) und zusammen sollte dies doch O(r²) ergeben?

    Ist dies so korrekt??



    Danke

    Christian

    Für den Worst Case gilt ja, dass alle Schritte bis zum Ende durchgeführt werden müssen, das heisst jede for Schleife bis zum Ende ausgeführt werden muss. Deine Notation ist zwar ziemlich merkwürdig, aber in diesem Fall sollte O(r²) eine annähernd passende Lösung sein, ungeschickte Sortier-Algorithmen haben diese Laufzeit auch im Std-Case, also sollte das schon so passen.