我阅读了stackoveflow建议的一些答案的问题。我正在按照cormen书中的算法介绍进行自学。那本书中所有的内容都清楚地解释了，但是唯一没有解释的是如何在合并排序分析中计算树的高度。
如果在后面的章节中对此进行了解释，则我仍在第二章中走得很远。
我想问是否最上面的节点被划分了2次，依此类推。它给了我ln（n）的高度，即log 2（n），如果我将主要问题分为五个子问题，该怎么办。那么会是日志5（n）吗？请解释这是如何以对数表示的，为什么不以某种线性术语来表示呢？
谢谢
递归树表示递归过程中的自调用。典型的mergsort调用自己两次，每次调用将输入的一半排序，因此递归树是一个完整的二叉树。
观察到高度增加的完整二叉树在其节点数上显示出一种模式：
height new "layer" total nodes
(h) of nodes (N)
1 1 1
2 2 3
3 4 7
4 8 15
...
L级的每个新层都有2 ^ L个节点（其中0级是根）。因此很容易看出，总节点N是h的函数，
N = 2^h - 1
现在求解h：
h = log_2 (N + 1)
如果您进行5向拆分和合并，则树中的每个节点都有5个子节点，而不是2个。该表将变为：
height new "layer" total nodes
(h) of nodes (N)
1 1 1
2 5 6
3 25 31
4 125 156
...
这里我们有N =（5 ^ 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）时间。无论是从理论上还是在实践中，您都不能忽略这笔费用！
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句