输入规模非均匀划分下树高计算：CLRS快速排序平均案例疑问

嘿，这个问题问得太到位了！当年啃CLRS第3版的时候，我也对着176页这个递归树高度的推导卡过一会儿，咱们一步步拆解清楚：

一、先明确递归树的生长逻辑 #

当快速排序每次按1:9的比例划分输入规模时，意味着每次选完pivot后，较大的那个子问题的规模是原问题的9/10（总规模n，分成1份和9份，大的部分就是9n/10）。递归树的高度，指的是从根节点（原问题规模n）到最底层叶子节点（子问题规模缩小到1，触发基准情况停止递归）的路径长度。

二、一步步推导高度公式 #

假设递归树的高度为h，那么经过h次递归划分后，最底层的子问题规模应该等于1（因为再往下就不需要递归了）。我们可以列一个等式：

原规模 × 每次缩小的比例^高度 = 基准情况规模
也就是：
n × (9/10)^h = 1

接下来解这个方程求h：

1. 两边同时取自然对数（或者任何底数的对数都可以，结果一致）：
   ln(n) + h × ln(9/10) = 0
2. 移项整理：
   h = -ln(n) / ln(9/10)
3. 注意到ln(9/10) = -ln(10/9)，代入后：
   h = ln(n) / ln(10/9)
4. 根据对数换底公式：log_b(a) = ln(a)/ln(b)，所以这个式子可以写成：
   h = log_(10/9)n

三、解释这个表达式的含义 #

• 从数学定义上看，log_(10/9)n表示以10/9为底数，n的对数，直白点说就是：把n每次乘以9/10（也就是缩小到原来的90%），直到变成1，需要执行的次数。
• 对比常规二叉树的最大高度log₂n：那是当每次划分完全平衡（1:1）时，子问题规模每次缩小到原来的1/2，所以需要log₂n次缩小到1。
• 这里的底数10/9是怎么来的？因为每次划分后大子问题是原规模的9/10，反过来想，每往上一层，规模就会变成下一层的10/9倍，所以用这个数作为对数底数，就能算出从规模1到n需要多少层，也就是递归树的高度。

补充一句：这个高度其实是这种1:9划分场景下的最坏递归深度（每次都选到导致1:9划分的pivot），在CLRS的平均情况分析里，它用来帮我们估算递归调用的层数上限，进而分析时间复杂度。

内容的提问来源于stack exchange，提问作者tinkuge