Почему Heapsort работает в $ theta (n log n) $ вместо $ theta (n^2 log n) $ времени?

Question

Я читаю раздел 6.4 об алгоритме Heapsort в CLRS, стр. 160.

HEAPSORT(A)  
1 BUILD-MAX-HEAP(A)  
2 for i to A.length downto 2  
3   exchange A[i] with A[i]
4   A.heap-size = A.heap-size-1  
5   MAX-HEAPIFY(A,1)

Почему время выполнения, согласно книге $ theta (n lg {n}) $, а не $ theta (n^2 lg {n}) $? BUILD-MAX-HEAP(A) берет $ theta (n) $, MAX-HEAPIFY(A,1) принимает $ theta ( lg {n}) $ и повторяется $ n-1 $ times (строка 3).

Answer 1

Давайте подсчитаем линию операций по линии. Вы строите кучу в линейное время. Затем вы выполняете цикл и выполняете операцию логарифмической времени $ N-1 $ Times. Другие операции занимают постоянное время. Следовательно, ваше время работы

$ qquad begin {align} & n + (n -1) log n + o (1) & = n + n log n - log n + o (1) & = theta ( n log n). end {align} $

Другими словами, как доминирует доминирует термин $ n log n $. То есть стоимость строительства кучи на линии 1 незначительна по сравнению с стоимостью выполнения петли.

Answer 2

У меня был другой вид на это. Я не мог игнорировать тот факт, что на шаге MAX_HEAPIFY в виде (который имеет порядок $ log n $, где $ n $ - размер кучи) получает уменьшенный размер кучи в каждой итерации. Так что для меня суммирование выглядело более или менее похоже на $ sum_ {k = 1}^{n-1} log k abstx log (n!) $. Теперь я знаю, что $ n! = Theta (n^n) $ таким образом $ log (n!) = Theta (n log n) $, но это никогда не было убедительным.