Zeitkomplexität von Bubblesort

Wissenschaft Informatik
#1

Hallo Leute,

Bubblesort-Algorithmen haben ja bekanntlich eine Zeitkomplexität von O(n²), wenn die Elemente der zu sortierenden Liste so ungünstig geordnet sind, dass eine maximale Anzahl von Vertauschungen erforderlich ist (–> „Worst-Case“)…
Soweit ganz gut, aber wie sieht es im „Best-Case“ aus? D.h. wenn die Liste eigentlich schon sortiert ist, und der Algorithmus nur noch einmal von vorne nach hinten „durchzugehen“ braucht, um die Elemente der Liste zu vergleichen, aber nix vertauschen muss…

Danke!

Stefan

#2

Hallo,
hängt davon ab, was gezählt wird. Vertauschungen gibt es keine aber es sind trotzdem quadratisch viele Vergleiche notwendig (zumindest bei der Standard-Variante).

Gruss
Enno

#3

…aber es muss doch einen Unterschied machen, ob nach jedem Vergleich eine Vertauschung stattfindet, z.B. von Datensätzen oder Strings, um eine alphabetische Reihenfolge zu bekommen, oder ob nach jedem Vergleich einfach gar nichts geschieht („Best-Case“)…

oder hängt das damit zusammen, dass bei der Komplexitätsbetrachtung nur der Grad des Polynoms (von der Funktion --> Zeitschritte = f (Problemgröße)) betrachtet wird, und die ggf. zusätzlich auszuführenden Vertauschungsaktionen dann nur als Proportionalitätsfaktor in diese funktioniale Abhängigkeit eingehen (und nichts am Grad des Polynoms ändern)?

Gruß, Stefan

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

#4

Hallo Stefan,

Bubblesort-Algorithmen haben ja bekanntlich eine
Zeitkomplexität von O(n²), wenn die Elemente der zu
sortierenden Liste so ungünstig geordnet sind, dass eine
maximale Anzahl von Vertauschungen erforderlich ist (–>
„Worst-Case“)…
Soweit ganz gut, aber wie sieht es im „Best-Case“ aus? D.h.
wenn die Liste eigentlich schon sortiert ist, und der
Algorithmus nur noch einmal von vorne nach hinten
„durchzugehen“ braucht, um die Elemente der Liste zu
vergleichen, aber nix vertauschen muss…

Der „best case“ besteht aus n-1 Vergleichen.
Allerdings wird Komplexitätsberechnung die Berechnung von „n“ nicht berücksichtigt.
Praktisch benötigst du n-1 „Datenvergleiche“ und n oder n+1 „Gültigkeitsvergleiche“ (Entweder in der FOR-Schlaufe (n) oder als Test auf „gültiges Element“, wenn das Ende der Liste mit einem Null-Eintrag (n+1) markiert ist).

MfG Peter(TOO)

#5

Hallo,
wenn man Vergleiche und Vertauschungen zählt, bleibt bei der Komplexitätsbetrachtung in der Landau-Notation

http://de.wikipedia.org/wiki/Landau-Notation

der Best-Case bei O(n2) (beim „klassischen Bubblesort“, der stur die zwei Schleifen durchnudelt). Hier wird in der Tat bei Polynomen nur der Grad berücksichtigt, allgemeiner der Anteil der Funktion, der am schnellsten wächst. Man kann den Best-Case allerdings leicht auf O(n) drücken, wenn man abbricht, falls in einem Durchlauf keine Fehlstellung entdeckt wurde und damit keine Vertauschung notwendig war.

Gruss
Enno