Рубрики

Время Сложность построения кучи

Рассмотрим следующий алгоритм построения кучи входного массива A.

BUILD-HEAP(A) 
    heapsize := size(A); 
    for i := floor(heapsize/2) downto 1 
        do HEAPIFY(A, i); 
    end for 
END

Быстрый просмотр приведенного выше алгоритма показывает, что время выполнения , так как каждый звонок в Heapify стоит и Build-Heap делает такие звонки.
Эта верхняя граница, хотя и правильная, не асимптотически жесткая.

Мы можем получить более жесткую границу, наблюдая, что время работы Heapify зависит от высоты дерева 'h' (которая равна lg (n), где n — количество узлов), а высоты большинства поддеревьев небольшой.
Высота «h» увеличивается, когда мы движемся вверх вдоль дерева. Строка-3 в Build-Heap запускает цикл от индекса последнего внутреннего узла (heapsize / 2) с высотой = 1 до индекса root (1) с высотой = lg (n). Следовательно, Heapify занимает разное время для каждого узла, что ,

Чтобы найти временную сложность построения кучи, мы должны знать количество узлов, имеющих высоту h.
Для этого мы используем тот факт, что куча размера n имеет не более узлы с высотой h.

Теперь, чтобы вычислить сложность времени, мы выражаем общую стоимость сборки-кучи как

(1)  

Шаг 2 использует свойства записи Big-Oh, чтобы игнорировать функцию потолка и константу 2 ( ). Точно так же на третьем шаге верхний предел суммирования может быть увеличен до бесконечности, так как мы используем обозначение Big-Oh.

Сумма бесконечного ГП (х <1)

(2)  

При дифференцировании обеих сторон и умножении на х мы получим

(3)  

Поместив результат, полученный в (3), в наш вывод (1), получим

(4)  

Отсюда доказано, что сложность времени для построения двоичной кучи ,

Ссылка :
http://www.cs.sfu.ca/CourseCentral/307/petra/2009/SLN_2.pdf

Эта статья предоставлена Чирагом Манвани . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Время Сложность построения кучи

0.00 (0%) 0 votes