Алгоритми та структури даних · Senior · Запитання 20 з 75
Як ефективно злити k відсортованих списків, де загалом n елементів?
- 1Склеїти їх і відсортувати результат: O(n)
- 2Зливати по одному в результат, що росте: O(n)
- ✓Правильна відповідь: Min-купа з k поточних голів: O(n log k)
Пояснення
Кожен крок знімає найменшу голову й кладе наступний елемент із того самого списку. Злиття по одному в найгіршому разі O(n × k); склеювання й сортування - O(n log n).