Gast123
unregistriert
 |
|
Hi Leute, ich hab hier folgende Aufgabe
Man kann eine ungeordnete Menge S von n Elementen dadurch sortieren, dass man zunächst einen binären Suchbaum für S aufbaut und dann einen Inorder Baumdurchlauf durchführt. Bestimmen Sie die Laufzeiten im besten und im schlechtesten Fall.
Also ich hab mir gedacht, ich bau den Suchbaum auf, indem ich nacheinander die Elemente in nen leeren Baum einfüge.
Im best case hat der die Höhe log_2(n) im worst case n.
Vergleiche bräuchte ich im worst case dann:
1+2+3+...+n = n/2(n+1)
Und im best case:
1+2*1+4*2+8*3+...+n*log_2(n)=1+sum(k=1 bis log_2(n)) [k*2^k]
Stimmt das so weit?
Der Inorder Durchlauf hat für beide Fälle dieselbe Komplexität denke ich, aber ich weiß nicht genau welche :/
Kann mir vlt. jemand n Tipp geben?
|
|
28.06.2009 11:42 |
|
|
