这一讲我们介绍递归树,他是迭代的一个图形表示。
我们先看看什么叫递归树。递归树呢,它是一个迭代计算的模型。
递归树的生成过程呢与迭代的过程是一致的。
递归树上所有的项的和 恰恰好就是迭代之后产生的和式中的那些个项。
那么我们对递归树上的项来求和就是迭代以后
方程的解。这个递归树和迭代的关系。
下来我们先介绍一下递归树是怎样来生成的。
递归树和迭代是有着密切关系的,是迭代的模型。
那么,一步迭代在在递归树上应该怎么表示呢? 我们来看看这个公式。假定这是递归方程,
左边是W(m),对规模为m的
它的工作量是W(m)。右边呢,出现一些个
子问题,规模是m1的子问题的工作量,同样的算法
一直到规模是mt的,一共有t个子问题;这个子问题的工作量,
这右边是递归计算这些个子问题的工作量。
那么在划分成这些个子问题,或者归结成这些个子问题
所需要做的工作,加上这些子问题求解完了以后把这些解
综合起来返回到原问题的解,这个综合的工作量
这两个工作量可以用下边的这个函数来表示。
比如说,这规模是m的第二道问题 划分过程和综合点的过程有f(m)一直到g(m)
这么多个工作量。这就是 一步迭代它所
或者递归它所产生的工作量的公式 掌握好这个递归方程。那么这样一部迭代
在递归树中怎么表示呢?我们把它分成两类的项。
带W的项这叫做函数项,不带W 的
这部分工作量在地递归树中我们要表达成一个根。
然后把这些个函数项,每个函数项作为这个根的儿子。
那我们来看一看左边这个公式它初始只有一个结点,就是这棵树只有一个结点;
它的工作量就正好等于方程的左部。右边呢,刚才我们说到了
把这个函数项部分作为儿子, 而这个非函数项的部分作为根。
所以这个f(m) 到g(m)都是根。
这边有几个儿子呢?有t个儿子。就是W(m1) 一直到W(mt),每个儿子是一个
结点然后这些个儿子都和这个函数项的副结点关连起来。这个仍一层迭代
它的树的表示。那么根据这个方程
这个值和右边这棵树上所有量的和应该改是相等的,
所以我们就可以看到这个结点的总值,和这个结点的总值是完全一样的。这个由这个递归方程
来决定的。那我们的迭代过程呢,就是把这个结点 用这棵树,把这个根节点
来替换这个W(m),替换过去以后这个树也就变成两层了。
那替换以后的树上所有结点的和,和替换前
这棵树的所有结点的和是完全一样的。这就是 迭代过程在递归树的表示可以通过这样一个两层的子树来表述。
那我们下边看看一个具体的表示的例子, 这是二分归并排序,二分归并排序呢
它是由原问题归结成两个子问题,每个规模是2/n。
那么,这一项呢是它里边儿的这个非函数的项。
这个情况下呢我们就把这个项作为根, 然后把这个W(n/2)两个子问题
对应的工作量作为两个儿子。这个的到了一个2层的树, 那这棵树的三个节点的量之和呢,正好好是
递归式的右部,而它来替换这个W(n),就是它的左部。
这就是右边的这个二层指数的表示。下面我们再利用这样的表示
来不断的用右边替换左边不断来生成 这棵树。生成规则就是一开始这棵树就有根结点,
它的值就正好等于W(n),那就是
这个初值。然後我们不断的继续下面的过程把这里边 包括函数的那些叶结点都用它
二层子树,右边的二层子树来替换它。
这样的替换过程,继续不断的来
替换这些个叶结点,就包括函项的叶结点,直到树中没有函数项为止。
那这个时候树中出现的就是只有初值了,这个迭代就到此,这棵树就生长了。
下面我们看看这个二分归并排序的它的生成过程。初始,
只有一个根结点,就是正好等于这个方程的左部。然後我们把这个结点
用它右部的二层的树来替换。所以一步替换以后呢这个
右边,这个二层的树它的根是n-1。然后有两个函数结点,是叶结点。
这个第一步迭代就由这棵树 生成了下面两层的树,那么对于这棵树来讲
这个W(n/2)还是函数项,那么这两个就得用它为根的这个二层的
树来进一步的迭代。我们看到这是刚才这个二层的树,然后对应
这个来进一步的迭代,金一部迭代以后呢,它就变成了一个 n/2-1和两个叶结点就是W
(n/4)的这个样的一个二层子树。这棵子树 它的结点的和正好跟W(n/2)相等。
因此我们就用这棵子树来替换了W(n/2)的这个 叶结点,这棵树就长了一层了。
右半边呢同样的替换,这时候这棵递归树呢已经变成有两层的,嗯,
就是多了一层,三层结点的树了。那么它下半叶结点的大小应规模是n/4了。
那么就可以按照这个规则不断的做下去,到这个叶结点
出现了初值的时候,这颗树就生成结束了。
按照刚才那个生成办法,跟一步 出现这两个节点和树叶,
然后再一步迭代,出现了第二个结点下边又有树叶;
这样做下去一直到最后出现初值都是1的时候截止。
截止的时候我们可以看到,把每一行
按照它的量,按行来相加,第一行是n-1。
那么第二行这两个量加起来呢,正好是n减掉2。
那么第三层的这些个加起来呢,正好是n减掉4。
可以发现它的规律,啊,这样的话我们就把所有的这些个都把它
计算出来,按行来计算出来。这就是第一行的,
然後第二行的,这个正好是n减掉2。
下一行的n-2的平方 最后是n减2的k减一次方。
把这些的项都加起来以后就是 递归树中所有的这些个量的总和。
因为我没一步迭代的时候都是 跟原始那棵树的值是一样的。因此这样加起来的总和呢就是原来
递推方程的解。我们来对这个求一下和,这是原来的方程,
这是第一层,n-1,第二层的量之和
的n-2。最后一层量的和n-2k-1。
那么对这个求和呢前面一共有多少个n呢?n出现了k次。
后边的是-1、-2一直减到2k-1,是一个等比数列
求和。这条和的结果2的k次方减1。
然后我们把k带进去,n和k有这样的关系, 其实把k带进去以后呢,就可以变成nlogn-n+1。
这就是可以利用递归树来对
这个递归方程来进行求解。这个迭代表示在树上会很
很简单。下面我们看一下这个方程的例子 如果这个方程要直接迭代的话,这个是原来的三分之一规模,
这项是三分之二的规模,是原来规模的三分之二。所以
这两个不一样大。不一样大,你迭代一次会出现两个不同的项 再迭代一次,就会出现四个不同的项。再迭代一次,
就是八个。所以,这样你要考察右边这个求和的时候,那个式子会比较复杂
如果我们要把它表达在树上的时候,就比较清晰了。很容易发现它的规则
那么右部这根是n,所以一步迭代有n有两个子树,
左边这个叶节点是T,n/3;右边是T是2n/3 就是一步迭代。然后T(n/3)和T(2n/3),
考虑左边再下一步迭代 这个规模是原始规模的三分之一
所以它迭代的结果应该左边应该还是右边的
是它上一层节点的三分之一。那么这个地方是n的话,
那这个n/3规模的话,这个地方出现的是n/3。对吧。那这个是n的话,
这个右边是规模变到三分之二,所以右边这个 迭代以后,这个值应该是三分之二倍的n
发现一个规律,就是这个值永远是它的三分之一,这个值永远是它的三分之二
那么下一次迭代的时候,这两个值就很容易写出来了。
那这个的三分之一就是九分之一,n/3的三分之二是2n/9
同样,它的三分之一,2n/9,这个的三分之二,4n/9 这是它的发展规律,就找到了。找到以后,
如果在树上,来把所有的量求和呢?一行一行的算。
第一行是n,第二行,这两个的和加起来正好是n
第三行,这四项加起来,九分之九倍的n也恰好是n
所以我们发现,,它这个和,每一行的加起来都是n, 但是这个路径的长度是不一样的。
左边这个缩小,每次都是父节点的三分之一, 所以它会比较快的就到达初值。
最右边这行,每个节点都是父节点的三分之二。
所以是比较慢的,会到达初值。应此右边的路径长,
左边的路径短。那做为上界的估计,我们就取这个最长的路径的长度就可以了。
到底下的部分,很可能它的左边的路径已经不存在了,
这个时候它的值加起来更小于n了,反正不超过n 因此我们把n做为每一行的上界。可以这样来估计写成O(n)。
然后我们把这个最长的路径的长度 计算一下它是多少步。这是原来的方程
地归树的层数,我们记做k的时候,那么可以满足下面的方程。
每递归一次,他就缩小到原来的三分之二。一共递归到k次以后,
缩小k次以后,变到初值1
这就是计算k的公式。那么根据这个公式呢。把这个2/3的k次方
移到右边来,那就变成3/2的k次方。左边这个n保留在这。
对它计算一下log
去对数。那么k应该是等于log以3/2
为底的对数,n啊,n的对数。所以这个就是它计算的最终结果。
原来我们在讲数学基础的时候讲过,log以谁为底,
它只是相差常数倍,它们是同样的阶,
所以我们可以把这个转换成log以2为底,它是同阶的。在大O的
含义下,它们的阶是一样的。都是同样的上界。因此我们就可以算出
这个算法,它最终的复杂度是n乘logn。这个logn就是k的阶。
这就计算出来了。因为每一层都是n吗。一共有k层。所以是n乘logn
这一章主要介绍了递归树。
递归树是迭代过程的一个图像表示 递归树它的生成规则是用右部
表达成一个二层的子树来不断的替换左部。
通过这一节,我们应该了解如何利用递归树来求解递归方程。
它的求解表示,比一般的迭代 会更加的简洁,更加的清晰。