Найти сложность времени?

Question

Предположим, что отсортированный список n/logn элементов отсортирован по лону. Затем укажите временную сложность создания отсортированного списка всех этих элементов? (подсказка: использование структуры данных кучи)

Как действовать, чтобы получить ответ с использованием структуры данных кучи?

Answer 1

Вы можете сделать это следующим образом:

1. Создать мин кучу размера = общее количество списков (LogN здесь) и вставьте 1-ый элемент во всех списках в кучу

2. Повторите следующий шаги № элементов в каждом списке * размер, который здесь n здесь.

   a) Получите минимальный элемент из кучи (минимум всегда в корне) и сохраните его в списке результатов.

   b) Замените корень кучи следующим элементом из списка, из которого извлекается элемент. Если в списке больше нет элементов, замените корень на бесконечность. После замены корня, heapify.

Таким образом, основным шагом является шаг 2, который запускает цикл n в этом случае. Каждый раз, когда heapify берет журнал (размер), который равен loglogn.

Следовательно, временная сложность: nloglogn.