Verständnisfrage Laufzeitanalyse

[ai.casselfornia]

Hallo Leute,

ich habe ein Verständnis Problem bei der Laufzeit Analyse des Bubblesort Sortierverfahren.

Wieso hat Bubblesort in seiner Standard Implementierung eine Best-Case Laufzeit von O(n)? Ich habe mal ein paar Experimente gemacht und die Anzahl der Vergleich bleibt bei mir immer O(n²), was für mich auch absolut logisch erscheint, da ja jedes Element mit jedem anderen in 2 verschachtelten for Schleifen verglichen wird.
Wenn also die Anzahl der Vergleiche immer quatratisch zur Datenmenge n ist, was ist dann mit Laufzeit gemeint? Die Anzahl der Vertauschungen ist doch im Best Case (aufsteigend sortiert) immer 0. Also wie kommt dieses O(n) zustande? Liegt es vielleicht an einer Optimierung, mit Prüfung auf vorzeitiges Ende?

Ich weiß, Bubblesort ist im Grunde der simpelste Algorithmus, aber ich tue mich auch nicht mit dem Verständnis der Funktionweise schwer, sondern eher mit dem Begriff der Laufzeit (oder Schritte).

Ich hoffe ihr könnt mir helfen.

Gruß,
Andre

 

[das Neutrum]

Es muss trotzdem über die gesamte Liste drüberiteriert werden, und da diese die Länge n hat ist der Aufwand auch n.

http://de.wikipedia.org/wiki/Bubblesort#Bester_Fall

 

[KamehamehaX10]

Best-Case wäre, wenn die Liste schon sortiert wäre. Also wird nur einmal durch jedes Element durchgegangen und geguckt ob das nächste Element kleiner (oder größer, je nachdem) ist. Dies ist nicht der Fall und es wird einfach weitergegangen, bis man einmal durch ist. Wenn dann festgestellt wird, dass im gesamten Durchlauf (n) keine Vertauschung stattgefunden hat, wird abgebrochen.

 

[ai.casselfornia]

Ja das verstehe ich ja, aber warum ist die Anzahl der Vergleiche in meinem Experiment immer quadratisch? Hab ich irgendwas falsch implementiert?

	public void sort(String[] array) {
		for (int i = 0; i < array.length; i++) {
			for(int j = 0; j < array.length - i - 1; j++) {
				if ( compareLess(array[j+1], array[j]) ) {
					swap(array, j, j + 1);
				}
			}
		}
	}

In jedem compareLess() zähle ich einen Vergleich (kleinerGleich) und in jedem swap() eine Tauschoperation.
Edit:
Liegt es an der in Wikipedia erwähnten Optimierung, "dass nach einer Iteration, in der keine Vertauschungen stattfanden auch in den restlichen Iterationen keine Vertauschungen mehr stattfinden"?
Dann habe ich es verstanden. Dann würde es aber bedeuten, dass Bubblesort in seiner einfachsten Implementierung immer eine Laufzeit von O(n^2) hat und nur durch diese Optimierung auf O(n) kommt. Sehe ich das richtig?

 

[SoDaTierchen]

Du hast es schon richtig verstanden: Bubblesort wird zur Laufzeitbetrachtung mit Bedingung auf vorzeitiges Ende angenommen. Weil es nur ein Byte und eine simple if-Abfrage ist, wird es generell in den Algorithmus hineingezählt.

Daher die Betrachtung: Average Case ~ Worst Case = O(n²), Best Case O(n). Das n kommt nur durch diese Optimierung auf Vorzeitigen Abbruch.

 

[ai.casselfornia]

Da war mein Fehler. Ich dachte, der Algorithmus sein so festgelegt und hatte mich halt gewundert, dass in der Literatur die Optimierung nicht im Pseudocode auftaucht. Dass ich da erst so spät drauf komme, ist wahrscheinlich der späten Uhrzeit zu schulden.

Vielen Dank für eure Hilfestellung