Stahlscher Algorithmus

Der Stahlsche Algorithmus bringt einen beliebigen Suchraum (danach: Findraum) in einen Zustand (die sog. Ordnung), in dem man auf jeden Gegenstand im Zimmer eine deutlich schnellere Zugriffszeit hat. Die solcherart schneller auffindbaren Gegenstände werden auch als aufgeräumt bezeichnet. Der Clou dabei ist der, dass man die Gegenstände zum Herbeiführen des Ordnungszustandes gar nicht bewegen muss!

Die Funktionsweise des Algorithmus' ist schnell erklärt, da er sich im Wesentlichen auf folgende zwei Fakten stützt:

1. Ein Raum mit nur einem einzigen darin enthaltenen Gegenstand ist aufgeräumt.
2. Ein Raum mit k Gegenständen, von denen jeder aufgeräumt ist, ist ebenfalls aufgeräumt.

Man teilt nun den Ausgangsraum ("Zimmer") rekursiv in immer kleinere Teilräume auf, bis sich am Ende in jedem Teilraum nur noch ein einziger Gegenstand befindet. Dadurch ist dann das Zimmer aufgeräumt. Wenn sich im Zimmer n Gegenstände befinden, so beträgt hernach die erwartete Zugriffszeit O(log n). Der Beweis sei sowohl dem geneigten wie auch dem aufrechten Leser zur Übung empfohlen.

 Siehe auch:  Mathematik | Mathemagie | Fäbscher Algorithmus