1. Dashboard
  2. Forum
    1. Unerledigte Themen
  3. Mitglieder
    1. Letzte Aktivitäten
    2. Benutzer online
    3. Team-Mitglieder
    4. Trophäen
    5. Mitgliedersuche
  4. Tutorial Bereich
  • Anmelden
  • Registrieren
  • Suche
Dieses Thema
  • Alles
  • Dieses Thema
  • Dieses Forum
  • Seiten
  • Forum
  • Lexikon
  • Erweiterte Suche
  1. Informatik Forum
  2. Webmaster & Internet
  3. Entwicklung

Laufzeit Analyse von Algorithmen

  • Christian81
  • 3. August 2005 um 16:43
  • Unerledigt
  • Christian81
    1
    Christian81
    Mitglied
    Punkte
    10
    Beiträge
    1
    • 3. August 2005 um 16:43
    • #1

    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 :tired_face: 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

  • linken_harmy
    1
    linken_harmy
    Gast
    • 4. August 2005 um 08:38
    • #2

    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.

  • Maximilian Rupp 27. Dezember 2024 um 12:06

    Hat das Thema aus dem Forum Programmieren nach Entwicklung verschoben.

Jetzt mitmachen!

Sie haben noch kein Benutzerkonto auf unserer Seite? Registrieren Sie sich kostenlos und nehmen Sie an unserer Community teil!

Benutzerkonto erstellen Anmelden

Benutzer online in diesem Thema

  • 1 Besucher

Rechtliches

Impressum

Datenschutzerklärung