wie lange braucht ein beliebiger Algorithmus mindestens zum erstellen eines binären suchbaums aus einer unsortierten Menge?
Wie lange braucht ein beliebiger Algorithmus mindestens zum erstellen eines binären Suchbaums aus einer unsortierten Menge von n vergleichbaren Elementen und warum?
3 Antworten
Für jedes Element muss sichergestellt werden, dass die Quasiordnung im aufzubauenden Baum beibehalten wird. Für Element i von i=1 bis n muss man also Ω(log(i)) (Tiefe des Baums mit i-1 Elementen) Vergleiche ausführen.
Für n Elemente ergibt sich daraus dann die Laufzeit Ω(n log(n)) (bilde Summe von log(i) über alle i)für einen beliebigen, vergleichsbasierten Algorithmus.
Man braucht mindestens n Schritte, weil die n Elemente ja nicht von allein in den Baum hüpfen. Und wenn alle Elemente gleich bei den ersten ein/zwei/drei Vergleichen eingefügt werden, bleibt man in 𝓞(n).
Das kommt ganz auf die Menge und Fächerung der Daten an, da ein Algorithmus auch nur an Ticks gebunden ist... Meine Vermutung