1. Was ist ein Algorithmus?
Ein Algorithmus ist eine eindeutige, endlich ablaufende Vorschrift zur Lösung einer konkreten Problemstellung. Er besteht aus einer klaren Abfolge von definierten Schritten (Operationen), die bei gegebenen Eingabedaten ein korrektes Ergebnis (Ausgabe) erzeugen.
Charakteristika
- Determinismus – bei gleichen Eingaben liefert der Algorithmus immer dieselbe Ausgabe.
- Endlichkeit – die Ausführung endet nach endlich vielen Schritten.
- Eindeutigkeit – jeder Schritt ist eindeutig beschrieben und für einen Computer oder Menschen ausführbar.
- Effizienz – beurteilt nach Zeit‑ (Laufzeit) und Platz‑ (Speicher) Aufwand (Komplexität).
2. Klassifikation von Algorithmen
3. Analyse von Algorithmen
- Zeitkomplexität – meist in Big‑O‑Notation angegeben (z. B. O(n log n), O(n²)).
- Platzkomplexität – Speicherverbrauch in Abhängigkeit von n.
- Best‑Case / Average‑Case / Worst‑Case – unterschiedliche Laufzeitbetrachtungen.
- Amortisierte Analyse – mittlere Kosten über eine Folge von Operationen (z. B. Push/Pop bei dynamischen Arrays).