Suchaufwand für balancierte Bäume
← Baumrotation | ● | Binary Space Partitioning →
Unter der Bedingung, dass ein Baum balanciert ist, besteht der Aufwand für die Operationen Einfügen, Suchen und Löschen aus jeweils einer Traversierung und einigen Zeigermanipulationen.
Der Gesamtaufwand für alle Baumoperationen läßt sich deshalb mit $c_1 log k+c_2$ beschreiben.
Für grosse k ist der konstante Aufwand zu vernachlässigen. Für Aufwandsabschätzungen ist man an der relativen Größenordnung für grosse k interessiert, so dass man lineare Vorfaktoren ebenfalls vernachlässigt.
Der Gesamtaufwand der balancierten Baumsuche ist also von der Ordnung $log k$. Man schreibt dafür kurz $O(log k)$ mit Hilfe der O-Notation (big-O).
Zum Vergleich: der Listen-Suchalgorithmus hat die Ordnung $O(k)$ und ist damit ordnungsmässig langsamer als die Baumsuche. Man schreibt hierfür $O(k) > O(log k)$.
Für grosse k ist ein Algorithmus mit einer kleineren Ordnung immer schneller. Für kleine k kann die Ordnung eines Algorithmus’ aber keine Aussage über die tatsächliche Geschwindigkeit machen, da diese für kleine k im Wesentlichen vom Vorfaktor abhängt, der stark unterschiedlich sein kann.
← Baumrotation | ● | Binary Space Partitioning →