nicht angemeldet
Hallo nochmal,
Der Algorithmus liegt übrigens in der Laufzeitklasse [latex]O(n + n\log n) = O(n\log n)[/latex], wenn mich nicht alles täuscht.
Ok, nochmal drüber nachgedacht: Das stimmt nur, wenn der Baum balanciert ist. Wenn er komplett unbalanciert ist (d.h. eine verkettete Liste), dann sieht's schlechter aus...
Ok, jetzt aber nochmal richtig: Wenn der Baum komplett balanciert ist und es genau [latex]n = 2^k - 1, k \in \mathbb{N}[/latex] Elemente im Baum gibt (best case), dann ist die Laufzeitklasse sogar nur [latex]O(2n + 1 + n) = O(n)[/latex]. Wenn der Baum überhaupt nicht balanciert ist (verkettete Liste), dann ist die Laufzeitklasse dagegen [latex]O(2n + 1 + 2^n + 1) = O(2^n)[/latex]. Alles andere liegt irgendwo dazwischen.
Viele Grüße,
Christian
Mein "Weblog" [RSS]
Using XSLT to create JSON output (Saxon-B 9.0 for Java)
How to tell the difference between a science fan and a scientist.