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递归树