Heap Сортировка Сложность

Question

Ниже приведен псевдокод пирамидальной сортировки на массиве

HEAPSORT(A) 
    BUILD-MAX-HEAP(A) 
    for i = A.length downto 2 
    exchange A[1] with A[i] 
    A.heapsize = A.heapsize - 1 
    MAX-HEAPIFY(A,1) 

Это мне ясно, что BUILD-MAX-КУЧА имеет сложность O (N) и MAX-HEAPIFY имеет сложность O (h) где h - высота кучи, которая имеет максимальное значение logn.

Я полностью не понимаю, почему у HeapSort есть сложность nlogn. Я понимаю, что у нас есть n итераций с каждым MAX-HEAPIFY. Но вызов MAX-HEAPIFY получает HEAP уменьшающегося размера на каждой итерации. Каким образом каждая итерация может иметь сложность O (lgn)? Плотно ли она связана? Где я могу увидеть математическое доказательство того же?

Answer 1

Заметим, что

log 1 + log 2 + log 3 + ... + log n 
= log (1 * 2 * 3 * ... * n) 
= log n! 

Теперь приближением Стирлинга,

n! ≈ sqrt(2πn) * (n/e)n

Итак:

log n! ≈ n * (log n/e) = n * (log n - 1) = n log n - n

which is O(n log n) because the n log n термин доминирует n термин (и O (журнал п) термин I исключено, потому что слишком сложно печатать с помощью MathJax).

Answer 2

Обозначение большого нота верхняя связанная. Как вы сказали:

MAX-HEAPIFY имеет сложность O (h), где h - высота кучи, которая имеет максимальное значение log n.

Нам все равно, уменьшается ли куча. Мы знаем, что в худшем случае, куча имеет высоту log n. Мы делаем это n раз, следовательно n log n.