Читать книгу Algorithmen und Datenstrukturen - Gunter Saake - Страница 84
Beispiel 3.15 Ackermannn-Funktion
ОглавлениеDie Ackermann-Funktion ist durch folgenden Algorithmus definiert:
| f(x, y) = | if x ≤ 0 | then y + 1 else |
| if y ≤ 0 | then f(x − 1, 1) | |
| else f(x − 1, f(x, y − 1)) fi fi |
Die Werte der Ackermann-Funktion wachsen unglaublich schnell an:
| f(0, 0) | 1 | |
| f(1, 0) | f (0, 1) 2 | |
| f(1, 1) | f (0, f(1, 0)) f(0, f(0, 1)) f(0, 2) 3 | |
| f(2, 2) | f (1, f(2, 1)) f(1, f(1, f(2, 0))) f(1, f(1, f(1, 1))) | |
| … f(1, 5) …f(0, 6) 7 | ||
| f(3, 3) | 61 | |
| f(4, 4) |
Da die Berechnung dieser Werte durch Addieren der Zahl 1 erfolgt, wächst natürlich auch der Berechnungsaufwand extrem an. Die Ackermann-Funktion ist durch ihr ungewöhnlich schnelles Wachstum insbesondere relevant in Komplexitätsbetrachtungen von Algorithmen.
Genau genommen handelt es sich bei der dargestellten Funktion um eine vereinfachte Variante, die auch als Ackermann-Peter-Funktion bezeichnet wird.
Mit diesen Beispielen schließen wir vorerst die Behandlung applikativer Algorithmen ab. Wir werden die Grundkonzepte in späteren Kapiteln wiederholt aufgreifen, z.B. bei der Korrektheit von Algorithmen und der Umsetzung von rekursiven Funktionsdefinitionen in Java-Programme.
