performance - 为什么归并排序的递归树的总层数是lg n + 1？

Question

我认为这个问题在这里很容易解释，但我正在查看“算法简介”第 3 版第 37 页，它说图 2.5 中递归树的总级别数是 lg n + 1，但我不明白为什么你必须 +1。谁能解释一下这背后的理由？谢谢

Answer 1

这棵树应该包含 N 个叶子。h级二叉树（根为1级）最多有2^(h-1)个叶子，所以我们断言2^(h-1) >= n，即h >= lg(n)+1 . 同时它应该是一个完整的二叉树。具有 h 级的完整二叉树至少有 (2^(h-2)+1) 个叶子，即 2^(h-2)+1<=n, h<=lg(n-1)+2

当n=2^k，k+2>h>=k+1，所以h=k+1=lg(n)+1，书上就是这样。

更重要的是，当n!=2^k时，会有ak，其中2^k>n>2(k-1)，我们有h>=lg(n)+1>k和h<lg(n)+ 2 < k+2，即 h = k+1 = ceil(lg(n)+1)。

总之，k = ceil(lg(n)+1)。其中ceil(lg(n)+1)表示不小于lg(n)+1的最小整数。

Answer 2

假设 N 等于 8。那么，我们有 4 个级别：

1. full array with size 8.
2. halves with size 4.
3. quarters with size 2.
4. eighths with size 1.

那是 lg n + 1。lg 8 = 3。lg 8 + 1 = 4。

Answer 3

我已经在视觉上详细解释了如何使用递归树计算归并排序的复杂性，看看这里