Algorithmus Laufzeit Logarithmisch

Question

man muss häufiger mal zeigen, dass ein entwickelter Algorithmus eine bestimmte Laufzeit hat, wobei ich im Allgemeinfall keine Probleme habe.

Problematisch wird es bei mir, sobald ich zeigen soll, dass die Laufzeit z.b. O(log n) oder ähnliches, was mit dem Logarithmus zu tun hat.

Ich soll z.B. zeigen, dass die Suche nach einem Element in einem beliebigen B-Baum der Ordnung t mit n Elementen mit binärer Suche eine Laufzeit von O(log t * log n) hat.

Wie gehe ich an so etwas heran? Bei quadratischer Laufzeit etc. ist es sinnvoll die Schleifendurchläufe zu betrachten. Hier macht das jedoch nicht so viel Sinn.

Liebe Grüße,
Marvin

Comments

Mir fällt beim Logarithmus als Erstes die harmonische Reihe ein. Habe aber keine Erfahrung mit Laufzeiten. Deshalb nur ein Kommentar. 

Answer 1

Durchschnittlicher Verzweigungsgrad bei Ordnung t ist 3/2 t. Mit binärer Suche (die Kinder eines Knotens sind sortiert mit wahlfreiem Zugriff) kann man in jedem Knoten in O(log₂(3/2 t)) das passende Kind auswählen. Verwende Logarithmusgesetze um zu zeigen dass O(log₂(3/2 t)) = O(log₂(t)) ist.

Ein B-Baum der Ordnung t und Höhe h kann n = t^h Einträge speichern (mit jeder Ebene ver-t-facht sich die Anzahl der Knoten). Daraus ergibt sich h = log_t(n). Um von der Wurzel zum Blatt zu gelangen müssen also log_t(n) Ebenen durchwandert werden.

Da auf jeder Ebene log₂(t) Vergleiche notwendig sind, und log_t(n) Ebenen existieren, sind insgesamt log₂(t)·log_t(n) Vergleiche notwendig.

Also hat Suche in einem B-Baum die Komplexität O(log(t)·log(n)).

Bonusfrage 1. Wohin ist beim Übergang von log₂(t)·log_t(n) Vergleichen zur Komplexität O(log(t)·log(n)) die Basis der Logarithmen verschwunden?

Bonusfrage 2. Warum werden B-Bäume überhaupt betrachtet? log(t) wird umso größer, je größer t wird. Warum wird nicht einfach ein Binärbaum verwendet, um log(t) möglichst klein zu halten?

Comments

Dankesehr.

1.   log₂(t)·log_t(n)/ (log(t)·log(n) ) = log₂(t)/log(t) = 1 / log(2) < unendlich  => Laufzeit O(log(t)·log(n))
Beim grün markierten weiß ich aber leider nicht,wie die Potenzgesetze dort angewendet werden. Ich denke mal das ist was simples, was ich gerade nicht sehe.

2. Das hat denke ich mal was mit dem Speicher zu tun. Wenn man viele Einträge pro Knoten hat und mit sehr großen Mengen arbeitet, liegt so immer nur ein Teil auf dem Hauptspeicher. Liege ich da richtig?