合并排序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）时间。您无论从理论上还是实践上都不能忽视这一成本！