Временная сложность пирамидальной сортировки во всех случаях равна nlog(n).
Но я не понимаю, почему, потому что мы должны вызывать n раз алгоритм heapify для дочерних двоичных деревьев с «i», которые уже имеют сложность ilog (i).
алгоритм пирамидальной сортировки по временной сложности
Ответы (1)
Операция heapify занимает O(lg(n)) времени. Когда вы меняете узел max/min с другим узлом из нижней части кучи, вам придется подтолкнуть этот узел обратно в самый низ. Поскольку имеется n элементов, а высота кучи равна lg(n), вы будете делать lg(n) перестановок по мере того, как ваш узел перемещается по куче вниз. Если вы повторите это n раз, время будет O(nlg(n)).
В худшем случае (ввод отсортирован, но в обратном порядке) и построение кучи, и сортировка будут O(nlg(n)). В лучшем случае (отсортированный ввод) построение будет O(n), а сортировка будет O(nlg(n)) (O(n), если ввод состоит из одинаковых значений). В среднем построение будет между лучшим и худшим случаем, сортировка будет O(nlg(n)).
person
An0num0us
schedule
18.11.2017
Я думал, что бинарное дерево такое, что у каждого родителя есть не более двух дочерних элементов.
- person Ronan Tarik Drevon; 19.11.2017
@RonanTarikDrevon Извините, я неправильно понял ваш вопрос. Я думал, ты имеешь в виду бинарные деревья поиска. В бинарных деревьях каждый ключ имеет не более двух дочерних элементов, и это единственное свойство бинарных деревьев.
- person An0num0us; 19.11.2017
