递归树

本文为《Algorithms》第一章的阅读笔记。

递归树是一种用来分析递归算法的可视化工具。

递归算法是一种将复杂问题简化为简单问题的算法。很特殊的是，简单问题和复杂问题有相同的形式，直至最简化状态，快速得出答案。也就是自己调用自己。

递归树根据算法形式将不同层次的问题放置在树的不同层级上。原始问题为树的根，最简化状态位于树的叶子结点。每一个节点的复杂度都是其所有子节点复杂度(SUM { T(n-1) })以及当前节点复杂度(f(n))的加和。

                          +---------+
                          |         |
                          |   T(n)  |
                          |         |
                          +----+----+
                               |
                 +-------------+--------------+
                 |             |              |
            +----+----+   +----+----+   +-----+----+
            |         |   |         |   |          |
            |  T(n/c) |   |  T(n/c) |   |  T(n/c)  |
            |         |   |         |   |          |
            +---------+   +---------+   +----------+

       +-+      +-+     +-+     +-+       +-+      +-+
       +-+      +-+     +-+     +-+       +-+      +-+

 +----------+     +----------+     +---------+     +----------+
 |          |     |          |     |         |     |          |
 |   T(a)   |     |   T(a)   |     |  T(a)   |     |   T(a)   |
 |          |     |          |     |         |     |          |
 +----------+     +----------+     +---------+     +----------+

每一层计算都产生了k次递归调用，拆分后的小问题变成了原来的c分之一，当前层的直观复杂度为f(n)。写成数学表达式，就是

T(n) = k * T(n/c) + f(n)

对于第p层，数学表达式成为

T(n) = SUM { k^i * f(n/(c^i)) | i = [1 -> p] }

递归算法的分析

考察每一层节点的复杂度的关系，也就是数值序列T(i) | i = [n -> 1]。

尽管该数值序列可以有各种各样的关系，但有几个特殊情形仍然可以尝试总结一下：

1. 几何递减：也就是T(n) = c * T(n-1) ｜ c > 1，每一层复杂度都是下一层复杂度的常数倍。因此T(n) = O(f(n))。最终的算法复杂度取决于叶子结点的复杂度。
2. 相同：那么T(n) = O(f(n)*L) = O(f(n)*log(n))。
3. 几何递增：也就是T(n) = c * T(n-1) ｜ 0 < c < 1，每一层复杂度都是下一层复杂度的常数倍。因此T(n) = O(n^(log(k)/log(c)))。最终的算法复杂度取决于叶子结点的数量。