In der Tabelle steht der Aufwand oder auch die Komplexität der einzelnen Sortieralgorithmen. Man bezeichnet ihn mit O(n).
n ist dabei die Anzahl der zu sortierenden Datensätze.
Mit dem Aufwand will man ungefähr abschätzen, wieviele Rechenschritte man zum Sortieren dieser Datensätze benötigt. Dabei interessiert weniger die genaue Zahl, sondern mehr um wieviel diese Rechenschritte ansteigen, wenn man mehr Datensätze hat. Also die Abhängigkeit von n.
Zum Beispiel: Stell Dir vor, es geht nicht ums Sortieren, sondern um eine andere Aufgabenstellung. Man soll n Datensätze (jeder besteht nur aus einer Zahl) einlesen und addieren und alle Datensätze anschließend auf 0 setzen. Man versucht es mit folgendem Code:
Quelltext
1:
2:
3:
4:
5:
6:
| Ergebnis:=0;
For i:=1 to n do
begin
Ergebnis:=Ergebnis+Datensatz[i];
Datensatz[i]:=0;
end; |
Und jetzt will man herausfinden, welchen Aufwand O(n) dieser Code hat.
Zählen wir also mal die Rechenschritte: Zuerst wird Ergebnis = 0 gesetzt, das ist unser erster Schritt. Dann wird die Schleife n mal durchlaufen. Und jedesmal zwei Rechenschritte ausgeführt. Macht also insgesamt 1+n*2 Rechenschritte.
Das ist aber nicht der Aufwand! Denn beim Aufwand O(n) interessiert - wie gesagt - nicht die genaue, exakte Zahl. Sondern nur die Abhängigkeit von n. Deshalb hat unser Beispiel einen Aufwand O(n)=n.
Wenn ein Sortieralgorithmus einen Aufwand von n hat ist er also - zumindest aber einer bestimmten Anzahl von Datensätzen - schneller als ein Algorithmus mit einem Aufwand von n² hat.
Ja, und BestCase ist der beste anzunehmende Fall. Wenn die Datensätze so glücklich vorsortiert sind, dass es besonders schnell geht. Worst Case ist der schlimmste anzunehmende Fall und AverageCase eben der Durchschnitt.
Und der zusätzliche Speicher? Einige Algorithmen sind halt sehr schnell, dafür brauchen sie aber extra viel Speicherplatz, um Ergebnisse zwischenzuspeichern. Man muss also bevor man einen Algorithmus auswählt gut abwägen, ob man viel oder wenig Speicher hat, oder ob man einen schnellen oder langsamen Rechner hat. Und nach diesen Kriterien entscheidet man sich dann für einen der Algorithmen.
Und wenn Du das alles ganz genau wissen willst, dann gibt es z.B. die Seite
ivs.cs.uni-magdeburg...ke/EAD/Skript20.html, oder jede Menge andere Seiten/Bücher/Vorlesungen über "Algorithmen und Datenstrukturen"
Na, erschlagen?
mein fehler 
