Heapsortは、$ theta（n^2 log n）$ timeの代わりに$ theta（n log n）$で実行されるのはなぜですか？

Question

CLRSのHeapsortアルゴリズムのセクション6.4を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 $が$ n log n $項が支配的であるように。つまり、1行目にヒープを構築するコストは、ループを実行するコストと比較して無視できます。

Answer 2

私はこれについてまったく別の見解を持っていました。この種のMAX_HEAPIFYステップ（$ log n $の順序があり、$ n $がヒープサイズ）が各反復でヒープサイズの減少を受信するという事実を無視することはできませんでした。私にとって、合計は多かれ少なかれ$ sum_ {k = 1}^{n-1} log k compx log（n！）$のように見えました。今、私はその$ nを知っています！ = theta（n^n）$その方法$ log（n！）= theta（n log n）$。しかし、それは決して説得力がありませんでした。