1.Max2二分递归的最差情况

如下图所示，最差的情况计算为 $T(n)=5n/3-2$ ，进一步计算，最好的情况应该是 $T(n)=3/2n-2$ 。
- 我个人理解的计算过程如下：
1. 两边加2，凑成等比数列；
  $T(n)+2=2(T(n/2)+2)$
2. 最差的情况是，每个递归基均是3个元素，且每次均需要比较3次，即 $T(3)=3$ ；
3. 根据结果反推，可知：
  $T(n)+2=2^{\log_{2}{n/3}}(T(3)+2)$
  其中，系数 $2^{\log{n/3}}$ 我个人是这样理解的：
  假设 $T(n)+2 =2^H(T(3)+2)$ ，这里的 $H$ 为一共向下递归了 $H$ 层。根据2所述，最差的情况均用到了 $T(3)=3$ 这个递归基，可以理解为递归至最底层时每组的元素必定是3个，将递归过程理解为一棵满二叉树，如下图，其中假设的层数H就是这个系数，因此： $H=\log_{2}{n/3}$
  想通了这一点，剩下的就是做代数运算了，
  $T(n)=5n/3-2$
对于最好的情况，每组递归基都是使用 $T(2)=1$ ，这样上述的 $H$ 变为 $2^H=n/2$ 。(此时递归到最底部每个分组中的元素个数为2，因此总组数应为 $n/2$ )

清华大学数据结构学习小结 第一章