Sortieren durch Suchbaum |
| 28.06.2009, 11:42 | Auf diesen Beitrag antworten » |
| Gast123 | Sortieren durch Suchbaum 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? |
|
|
|
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
