Algorithmen und Datenstrukturen · Senior · Frage 20 von 75
Wie führt man k sortierte Listen mit insgesamt n Elementen effizient zusammen?
- 1Verketten und das Ergebnis sortieren: O(n)
- 2Nacheinander in ein wachsendes Ergebnis zusammenführen: O(n)
- 3Ein Min-Heap der k aktuellen Köpfe: O(n log k)
Antwort zeigen
Richtige Antwort: Ein Min-Heap der k aktuellen Köpfe: O(n log k)
Erklärung
Jeder Schritt nimmt den kleinsten Kopf und legt das nächste Element derselben Liste nach. Nacheinander zusammenzuführen ist im schlimmsten Fall O(n × k); Verketten und Sortieren ist O(n log n).