Achtung: Wichtig für uns ist das asymptotische Verhalten für größere n, bei kleineren n kann ein Algorithmus höherer Komplexität mitunter schneller sein!
Bei der Untersuchung eines Algorithmus unterscheidet man 3 Fälle:
Bevor wir zu den einzelnen Algorithmen kommen, wollen wir das Wichtigste nicht außer Acht lassen: Die Komplexität. Komplexität beinhaltet messbare oder berechenbare Merkmale von Algorithmen, so Laufzeit (Wie lange "arbeitet" das Programm, bis es abbricht?) und Speicherbedarf des Programmes, das diesen Algorithmus benutzt.
Die Tabelle zeigt die Größenordnung des Aufwands bzw. der Komplexität.
Achtung: Wichtig für uns ist das asymptotische Verhalten für größere n, bei kleineren n kann ein Algorithmus höherer Komplexität mitunter schneller sein!
Bei der Untersuchung eines Algorithmus unterscheidet man 3 Fälle:
Best-Case-Analyse: erforderliche Laufzeit für den günstigsten Fall wird ermittelt
Average-Case-Analyse: erforderliche Laufzeit für den mittleren Fall (Mittelwert, Erwartungswert) wird ermittelt
Worst-Case-Analyse: erforderliche Laufzeit für den ungünstigsten Fall wird ermittelt
