Unter einem Algorithmus versteht man eine Handlungsanweisung oder eine Rechenvorschrift zur Lösung eines Problems.
Beispiel: Gegeben zwei natürliche Zahlen 36 und 64, gesucht ist der größte gemeinsame Teiler (ggt).
Für dieses Problem gibt es eine Lösung von Euklid, die man in ein (Python-)Programm umsetzen kann.
Welche Anforderungen müssen Algorithmen erfüllen?
Sie sollen korrekt sein, der Algorithmus soll also für eine bestimmte Eingabe auch stoppen.
Sie sollen effizient sein. Wir nennen einen Algorithmus effizient, wenn er möglichst wenig Rechenzeit oder Speicherplatz benötigt.
Die Analyse der Rechenzeit nennt man auch Laufzeitanalyse, und man kann Algorithmen nach ihrer Laufzeit in Klassen einteilen (Komplexität eines Algorithmus). Die Laufzeit hängt meistens von der Größe n der Eingabe ab, Beispiel: Es macht einen Unterschied, ob wir n = 10 Elemente sortieren wollen oder n = 1 000 000.
Für die Laufzeitanalyse kann man drei Fälle unterscheiden:
Der beste Fall (best case) → Sortieren eines schon sortierten Feldes.
Der schlechteste Fall (worst case) → hier benötigt der Algorithmus für eine bestimmte Eingabe die meiste Zeit.
Der Durchschnittsfall (average case): Man spricht von der durchschnittlichen Laufzeit, ein Zeitmaß, das auf statistischen Daten beruht. Diesen Fall haben wir beim letzten Mal durch eine Zeitmessung gezeigt, ansonsten findet man hier alles weitere (auch in Python!).
Bei der Worst-Case-Analyse ordnet man bestimmten elementaren Operationen wie z. B. einem Vergleich, einer Addition oder einer Multiplikation eine bestimmte Laufzeit zu, anschaulich wären das die Zyklen, die ein (abstrakter) Prozessor für die Ausführung der Addition oder des Vergleichs benötigt. Man nennt den Prozessor abstrakt, weil natürlich konkrete Prozessoren für eine Addition unterschiedlich lange benötigen. Der abstrakte Prozessor hat sogar einen Namen: RAM (= Random Access Maschine, ein Maschinenmodell, das uns in Q3 begegnet).
Ordnet man den elementaren Operationen eine konstante Laufzeit c zu, so betrachtet man im nächsten Schritt Konstruke wie die Zuweisung (Laufzeit: konstant), die Verzweigung (→ Fallunterscheidung) oder die Schleife (Laufzeit n, falls die Eingabe n Elemente enthält). Die folgende Tabelle gibt eine Übersicht über die Komplexität von Algorithmen in Abhängigkeit von der Länge n der Eingabe:
| Wachstumsart | Prototyp | Grundeigenschaft |
|---|---|---|
| logarithmisches Wachstum | f(n) = log(n) (mit beliebiger Logarithmenbasis) | Wenn n sich verdoppelt, dann wächst f(n) um einen konstanten Betrag. |
| lineares Wachstum | f(n) = n | Wenn n sich verdoppelt, dann verdoppelt sich f(n) ebenfalls. |
| logarithmisch-lineares Wachstum | f(n) = n*log(n) (mit beliebiger Logarithmenbasis) | |
| quadratisches Wachstum | f(n) = n2 | Wenn n sich verdoppelt, dann vervierfacht sich f(n). |
| kubisches Wachstum | f(n) = n3 | Wenn n sich verdoppelt, dann verachtfacht sich f(n). |
| polynomiales Wachstum | f(n) = nk | Wenn n sich verdoppelt, dann vervielfacht sich f(n) mit 2k. |
| exponentielles Wachstum | f(n) = bn | Wenn n sich um 1 erhöht, dann vervielfacht sich f(n) mit b |
Probleme mit exponentiellem Wachstum findet man häufig in der Kombinatorik (→ n!).
Beispiel: Das Problem des Handlungsreisenden. Ein Handlungsreisender soll auf einer Tour insgesamt 20 Städte besuchen, finde die optimale Route für den Handlungsreisenden. Der Problemraum ist hier endlich: Es gibt ja "nur" 20! Möglichkeiten. Aber: 20! ≈ 2,433 ⋅ 1018.
Umgekehrt kann man zeigen, dass Sortieren im worst-case zur Klasse der Algorithmen mit logarithmisch-linearem Wachstum gehört, es gibt aber Sortieralgorithmen mit quadratischer Laufzeit (Welche?).