Algorytmy i struktury danych · Senior · Pytanie 20 z 75
Jak wydajnie scalić k posortowanych list z łącznie n elementami?
- 1Połączyć je i posortować wynik: O(n)
- 2Scalać po jednej do rosnącego wyniku: O(n)
- ✓Poprawna odpowiedź: Min-kopiec k bieżących głów: O(n log k)
Wyjaśnienie
Każdy krok zdejmuje najmniejszą głowę i wkłada następny element z tej samej listy. Scalanie po jednej to O(n × k) w najgorszym razie; łączenie i sortowanie to O(n log n).