比较树

copy 自邓俊辉《数据结构（第三版）》 2.7.4

基于比较的算法，即 CBA(comparison-based algorithm)，其执行情况可以用一棵比较树来描述，利用比较树的叶子节点数和树高度可以很直观地感觉到基于 CBA 的算法的下界

称苹果

三个苹果 A, B, C 中有一个的重量不同，用一杆称最少称几次才能找出不同的重量

基于比较树这样考虑：最终结果有三种，分别是 A 重量不同，B 重量不同，C 重量不同，因而比较树最少有三个叶子节点，因而树高度必然大于等于 2，于是不可能只比较一次就得到答案

CBA 排序下界

排序结果最坏情况下一共有多少种？

答案是 $n!$

因此比较树的高度不小于 $\log (n!)$

基于 stirling 近似，可以得到比较树的高度不低于 $\log (\sqrt{2\pi n}(\frac{n}{e}{)}^n)=\log (\sqrt{2\pi n})+n\log \frac{n}{e}$

于是确定了一个下界

从结果种数倒推

就像把有 $f(n)$ 个元素的集合分为 $n$ 个非空集合，至少需要分多少次一样

信息论

十位二进制数 0b0101001111，让人随机猜数，猜对的概率是 $\frac{1}{2^{10}}$

如果告诉他第一位是 0，那么他猜对的概率上升到 $\frac{1}{2^9}$

可知，如果告诉他全部 10 位，则猜对的概率为 $1$

比较树就可以看作这样一个逐渐获取信息的过程：一共 $n$ 种结果，其中只有一个是对的，那么猜中它的概率就是 $\frac{1}{n}$

将 $n$ 种结果看作 $[0,n-1]$ 这 $n$ 个数字，比较树的每一层就像获取了正确答案的二进制的一位，要保证获取到能唯一确定正确结果的信息量，就至少要获取 $\log n$ 位信息