01、迭代法

迭代法就是迭代的方式展开方程的右边，直到没有可以迭代的项为止，这时通过对右边的和进行估算来估计方程的解。

下面给出一个用迭代法求解的例子。
【例1】汉诺塔问题

3根圆柱a、b、c，其中a上面串了n个圆盘。这些圆盘从上到下是按从小到大顺序排列的，大的圆盘任何时刻不得位于小的圆盘上面。每次移动一个圆盘，最终将所有圆盘移动到c上，该如何移动？

该问题的算法描述如下：

参数n代表问题的规模，耗时用T(n)表示，规模为n-1时的耗时为T(n-1)。当规模为1时，只需要移动一步即可，耗时为O(1)。当规模大于1时，先将n-1个圆盘移动到b，耗时T(n-1)；然后将剩下的1个圆盘移动到c，耗时O(1)；最后将n-1个圆盘移动到c，耗时T(n-1)。故汉诺塔问题的时间复杂度递推方程如下：

令c=O(1)，用迭代法求解过程如下：

故算法hanoi的时间复杂度为O(2n)。

02、递归树

递归树是迭代过程的一种图像表述，常被用于求解递推方程，它的求解表示比一般的迭代会更加的简洁与清晰。

递归树是迭代计算的模型，它的生成过程与迭代过程一致，递归树上所有项恰好是迭代之后产生和式中的项，对递归树上的项求和就是迭代后方程的解。不妨设递推方程的一般形式为：

其中，n为原问题的规模；mk(k=1,2,…,i)为划分的子问题的规模；f(n)表示分解子问题和归并子问题的解为原问题的解所消耗的总时间。
递归树生成规则如下：

(1) 初始时递归树只有根节点T(n)；

(2) 将递归项叶节点的迭代式T(n)表示成二层子树，父节点为递归前分解子问题和递归后归并子问题的解消耗的时间f(n)，子节点为子问题的递归项T(mi),i=1,2,…,i。该操作一直持续到无递归项为止。
【例2】根据二分查找算法的时间复杂度递推方程，用递归树求解二分查找的时间复杂度。

解：第一步，递归树中只有T(n)，如图2所示。

第二步，将递归项T(n)表示成两层子树，用两层子树代替T(n)，令c=O(1)，如图3所示。

■ 图2根节点 ■ 图3两层子树代替根节点

第三步，将递归项T(n/2)表示成两层子树，用两层子树代替T(n/2)，如图4所示。

以此类推，直到没有递归项为止，如图5所示。

二分查找算法的时间复杂度为clog2n，即O(log2n)。

■ 图4两层子树代替T(n/2) ■ 图5递归树