Die Situation stellt sich wie folgt dar:-
Wir haben n Zahlen und wir haben drucken sie in sortierter Reihenfolge. Wir haben Zugang zu auf eine ausgewogene Wörterbuch-Datenstruktur, die die Operationen serach, Einfügen, Löschen, Minimum, Maximum jeweils in O(log n)-Zeit unterstützt.
Wir wollen die Zahlen in sortierter Reihenfolge in O(n log n)-Zeit mit nur die Einfügung und das In-Order Traversal.
Die Antwort auf diese Frage lautet: -
Sort()
initialize(t)
while(not EOF)
read(x)
insert(x,t);
Traverse(t);Nun ist die Frage, wenn wir die Elemente in der Zeit "n" zu lesen und dann durchlaufen die Elemente in "log n" (in-Order-Traversal) Zeit, dann die Gesamtzeit für diesen Algorithmus (n + logn) Zeit, nach mir. Erläutern Sie bitte den weiteren Verlauf dieses Algorithmus für die Zeitberechnung. Wie wird die Liste in O(nlogn)-Zeit sortiert?
Danke.
