Выбор ответа Middle Куча обновлено
Слияние k отсортированных списков
Вопрос
Слить k отсортированных списков общей длиной N. Какая сложность с min-кучей из голов списков?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: O(N log k). В куче всегда не больше k элементов.
Варианты ответа
- O(N · k)
- O(N log N)
- O(N log k)правильный ответ
- O(k log N)
Разбор
В куче всегда не больше k элементов. Каждый из N элементов один раз попадает в кучу и один раз извлекается: O(N log k).
- O(N · k) даёт поиск минимума перебором голов.
- O(N log N) даёт склейка и сортировка.
- O(k log N) меньше N и невозможно: каждый элемент нужно хотя бы вывести.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.