合併排序lg（n）+1遞歸樹的高度怎麼樣+1

Question

我按照stackoveflow的建議閱讀了幾個問題。我正在按照cormen book的算法介紹我的自學。在該書中所有的東西都已被清楚地解釋，但唯一沒有解釋的是如何在合併排序分析中計算樹的高度。

如果在後面的章節中解釋過，我仍然在第2章還沒有走得太遠。

我想問一下，如果最頂端的節點被劃分2次，依此類推。它給我一個ln（n）的高度，它是log （n）如果我把主要問題分成五個子問題怎麼辦？那麼它會被記錄爲（n）嗎？請解釋這是怎麼表示在對數以及爲什麼不在一些線性項？

謝謝

Answer 1

遞歸樹表示遞歸過程中的自我調用。典型的mergsort自己調用兩次，每次調用排序一半的輸入，所以遞歸樹是一個完整的二叉樹。

觀察增加的高度在它們的節點的數字中顯示的圖案的該完整的二叉樹：

height new "layer" total nodes 
(h)  of nodes  (N) 
1  1   1   
2  2   3 
3  4   7 
4  8   15 
... 

在L電平的每個新層具有2 ^大號節點（其中0級是根）。所以很容易地看到，總節的N作爲h的函數是

N = 2^h - 1 

現在解決了H：

h = log_2 (N + 1) 

如果你有一個5路分割與合併，然後在每個節點樹有5個孩子，而不是兩個。表變爲：

height new "layer" total nodes 
(h)  of nodes  (N) 
1  1   1   
2  5   6 
3  25   31 
4  125   156 
... 

在這裏，我們有N =（5 2 H - 1）/ 4，求解小時，

h = log_5 (4N + 1) 

通常，對於一個K-路合併，樹具有N個=（K^h - 1）/（K - 1），所以高度由下式給出：

h = log_K ((K - 1)N + 1) = O(log N) [the log's base doesn't matter to big-O] 

但是，要小心。在K-way mergesort中，選擇要合併的每個元素需要Theta（log K）時間。您無論從理論上還是實踐上都不能忽視這一成本！