Bellman-Algorithmus
aus Wikipedia, der freien Enzyklopädie
Der Algorithmus von Bellman konstruiert aus einer gegebenen Schlüsselliste und einer korrespondierenden Suchwahrscheinlichkeit einen optimalen binären Suchbaum. Der Algorithmus basiert auf dem von Richard Bellman 1957 gefundenen Satz über optimale mittlere Suchdauern in binären Suchbäumen (siehe Idee).
[Bearbeiten] Idee
Der Bellman-Algorithmus ist ein Beispiel für Dynamische Programmierung.
[Bearbeiten] Komplexität
Das Ausprobieren sämtlicher Möglichkeit hat exponentielle Komplexität. Durch das verwenden von Teilergebnissen (Konzept der Dynamischen Programmierung) kann das Aufzählen der (sinnvollen) Möglichkeiten allerdings auf kubischen Aufwand reduziert werden. Der Algorithmus liegt also in der Komplexitätsklasse O(n3).
