Komplexität / Frage zu SelectionSort(MinSort)

SeppJ

freakC++ schrieb:

Kannst Du mir eine gute Quelle nennen? Wikipedia reicht anscheinend nicht!

Mich.

Aber ich habe heute keine Zeit einen langen Beitrag darüber zu schreiben. Vielleicht hat jemand anderes ja mehr Zeit oder eine andere gute Quelle.

freakC++

Hallo,
danke für den Link. Ich werde mir die Vorlesung heute mal anschauen.

Du musst auch keinen langen Beitrag schreiben ;). Solange Du meine Fragen kurz beantwortest ist mir schon sehr geholfen. Da ich aber weiß, dass Du das machst, ist ja alles im grünen Bereich

Bis bald
lg, freakC++

Bashar

Bei der Komplexität ignoriert man vereinfacht gesagt konstante Vorfaktoren und betrachtet nur dominante Terme, man interessiert sich nur für eine generelle Aussage zur Wachstumsgeschwindigkeit der Laufzeit, wenn man die Größe der Eingabe erhöht.
Es ist ja z.B. klar, dass ein und derselbe Selection-Sort auf unterschiedlichen Rechnern oder mit unterschiedlichen Compilereinstellungen unterschiedlich lange läuft, oder dass derselbe Algorithmus in einer anderen Sprache eine andere Laufzeit haben kann. Wenn man diese Einflüsse alle rausrechnet kommt man zu Aussagen wie "Die Laufzeit ist asymptotisch proportional zum Quadrat der Länge der Eingabe", woraus man etwa absehen kann, dass das Verfahren für 1000 zu sortierende Elemente 100mal solange braucht wie für 100 Elemente, und für 10000 Elemente nochmal 100mal solange ...
Man schreibt das als O(n^2) (wobei das große O bedeutet, die Laufzeit ist *höchstens* asymptotisch proportional zum Quadrat von n, es gibt auch noch andere Landau-Symbole)
Selection-Sort und Bubble-Sort haben nun durchschnittlich (d.h. wenn man über alle möglichen Eingangsverteilungen mittelt) und im Worst-Case eine Laufzeit von O(n^2). Bessere oder schlechtere Implementierungen äußern sich in Vorfaktoren oder gegenüber n^2 "kleineren" Termen, so dass sie in der O-Notation rausfallen. Echt schneller als diese beiden Algorithmen sind z.B. Heap-Sort, Merge-Sort oder Quicksort, die im Durchschnitt O(n log n) Laufzeit haben.

freakC++

Hallo,
danke für die Antwort. Bedeutet dies also, dass die Effiziez von BubbleSort und MinSort gleich ist. Beide haben dann diese Cases:

Best Case: : Ο=n
Worst Case: Ο=(n(n-1))/2

Vielen Dank
lg, freakC++

SeppJ

freakC++ schrieb:

Bedeutet dies also, dass die Effiziez von BubbleSort und MinSort gleich ist.

Ja, wobei Bubblesort in der Regel größere Konstanten hat. Aber wenn ein sehr geschickter Programmierer Bubblesort schreibt und ein sehr ungeschickter Programmierer MinSort schreibt, könnten beide gleich schnell sein.

Jedoch hat MinSort meines Wissens nach einen BestCase von O(n^2), ist da also tatsächlich schlechter als Bubblesort. Was aber wie schon erwähnt völlig unbedeutend ist.

Fazit: Für größere Datenmengen sind beide unbrauchbar. Und auch bei sehr kleinen Datenmengen gibt es Verfahren die (normalerweise) kleinere Konstanten aufweisen.

(Definition von Konstanten:
Der Zeitfaktor der noch an die Komplexitätsklasse ranmultipliziert wird um die wirkliche Laufzeit zu bekommen. Diese ist stark implementierungsabhängig.)

freakC++

Hallo zusammen,
also ich habe mir mal diese Vorlesung angeschaut und bin hellauf begeistert. Soweit ich das verstanden habe, schaut man also nur auf die relative Geschwindigkeit, schmeißt alle Konstanten heraus, um somit auch plattformunabhängig zu sein.

Wichtig ist wohl dieser n0 Punkt. Wenn ich beispielsweise einen Algorithmus habe, der die Laufzeit O(n^2) hat und ein anderer O(n^3), dann schneiden die sich. Wenn ich den ersteren auf einem Pc laufen lasse und den letzteren auf einem Supercomputer und gegen unendlich gehe, dann wird der PC gewinnen, obwohl er eine niedrigere Leistung hat.

Ok, doch ich hatte eine Klausuraufgabe, in der eine Zahlenfolge gegeben war und man sollte nun herausfinden, wie viele Vergleiche und Vertauschungen (best und worse case) mit dem BubbleSort und dem MinSort nötig sind. Ist das nicht schwachsinnig, denn da kommt es wirklich auf die Implementation an!!!

Vielen Dank
lg, freakC++

freakC++ schrieb:

Ok, doch ich hatte eine Klausuraufgabe, in der eine Zahlenfolge gegeben war und man sollte nun herausfinden, wie viele Vergleiche und Vertauschungen (best und worse case) mit dem BubbleSort und dem MinSort nötig sind. Ist das nicht schwachsinnig, denn da kommt es wirklich auf die Implementation an!!!

Nein. Die Implementierung sollte nichts am Algorithmus ändern. Wenn man bei der Implementierung vom Original abweicht, dann kann sich das natürlich ändern, aber dann implementiert man eben auch nicht mehr den Algorithmus (sondern irgendeine Variation dessen)

freakC++

Mmhh, ok.

Also in der Vorlesung wurde gesagt, das InsertSort den Worst Case von O(n^2) hat, also wie bei BubbleSort und MinSort. Weiter oben habe ich jedoch geschrieben, dass der Worst Case Ο=(n(n-1))/2 ist. Was ist nun richtig?

2.) Schaut euch mal bitte die Tabelle auf dieser Seite an:

http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html

Da sind beispielsweise bei BubbleSort und SelectionSort best/worse Case immer gleich aber laut Vorlesung gilt doch:

Worst Case: θ(n^2 )
Best Case: θ(n)

Ich habe in diesem Gebiet noch gar keine Erfahrungen gemacht, weshalb die Fragen vielleicht ein bisschen doof sind :xmas1:

Vielen Dank
lg, freakC++

SeppJ

freakC++ schrieb:

Mmhh, ok.

Also in der Vorlesung wurde gesagt, das InsertSort den Worst Case von O(n^2) hat, also wie bei BubbleSort und MinSort. Weiter oben habe ich jedoch geschrieben, dass der Worst Case Ο=(n(n-1))/2 ist. Was ist nun richtig?

Rechne doch mal nach, von welcher Ordnung (n(n-1))/2 ist. Das ist O(n^2).

2.) Schaut euch mal bitte die Tabelle auf dieser Seite an:

http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html

Da sind beispielsweise bei BubbleSort und SelectionSort best/worse Case immer gleich aber laut Vorlesung gilt doch:

Worst Case: θ(n^2 )
Best Case: θ(n)

Ich habe in diesem Gebiet noch gar keine Erfahrungen gemacht, weshalb die Fragen vielleicht ein bisschen doof sind :xmas1:

Vielen Dank
lg, freakC++

Ihr habt in der Vorlesung offenbar das gemacht, was auf der Seite als "Modified Bubble sort" bezeichnet wird.

freakC++

Hallo,
ups, ja...mmh!

Ne, mit Vorlesung meine ich den Link der ganz am Anfang gepostet wurde. Ich bin noch in der Schule, weshalb die Fragen manchmal blöd sind....

Ich kann aber nun schreiben (denn so habe ich wikipedia) verstanden, dass für

Insert, Selection, Shake und Bubble gilt:

Worst Case: θ(n^2 )
Best Case: θ(n)

Doch was meint dann meine gepostete Website?

Vielen, vielen Dank
lg, freakC++

life

Deine gepostete Webseite hat recht und stimmt dabei mit den Infos auf Wikipedia und der Vorlesung überein.