归并排序中递归树的高度log(n)+1是怎么来的

我按照 stackoveflow 的建议阅读了一些问题和答案。我正在遵循 cormen 的《算法简介》一书进行自学。那本书里已经解释得很清楚了，但唯一没有解释的是如何在合并排序分析中计算树的高度。

如果在后面的章节中对此进行解释的话，我仍然在第 2 章中，还没有走多远。

I want to ask if the top most node is divided 2 times and so on. It gives me a height of ln(n) which is log₂(n) what if i divide the main problem in five subproblems. Would it have been log₅(n) then? Please explain how is this expressed in logarithm as well why not in some linear term?

Thanks

递归树代表递归过程中的自调用。典型的合并排序会调用自身两次，每次调用对一半的输入进行排序，因此递归树是一个完全二叉树。

观察高度递增的完整二叉树在其节点数量上显示出一种模式：

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 个子节点，而不是两个。该表变为：

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，

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 路归并排序中，选择要合并的每个元素需要 Theta(log K) 时间。无论在理论上还是在实践中你都不能忽视这个成本！