《算法设计与分析》一一2.3 “分治递归”求解-阿里云开发者社区

开发者社区> 华章出版社> 正文

《算法设计与分析》一一2.3 “分治递归”求解

简介: 本节书摘来自华章出版社《算法设计与分析》一 书中的第2章,第2.3节,作者:黄宇 著 ,更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.3 “分治递归”求解

递归是一种基本的算法设计方法,而递归算法的代价往往可以用递归方程来描述,因而解递归方程就成为递归算法分析的重要技术。分治策略(divide and conquer)是一种简单而有效的算法设计策略(详见第三部分各章节的讨论),源自于分治算法分析的一类特定形式的递归方程我们称之为“分治递归”(divide and conquer recursion)。本节着重讨论“分治递归”的求解方法。
2.3.1 替换法
有一种“大胆假设,小心求证”的方法可以帮助我们解“分治递归”。其核心原理是,如果能够猜测递归式的一个解,我们往往可以采用所谓替换法(substitution method)来较容易地证明它。替换法的本质是数学归纳法,只不过针对解递归的特定场合我们做了一些形式上的设定。我们通过一个具体的例子来展示替换法的证明过程。
对于递归式T(n)=2T(n/2)+n,我们猜测T(n)=O(n log n)。为了证明这一结论,我们将渐近记号转换为更容易处理的不等式形式。要证明T(n)=O(n log n)也就是要证明对于某个常数c>0,T(n)≤cn log n成立。按照数学归纳法,假设对于小于n的参数情况,这一不等式对于某个选定的常数c已经成立,下面来看参数为n的情况。基于归纳假设,我们有T(n/2)≤c・n/2・log(n/2),所以:T(n)=2T(n/2)+n
≤2c・n/2・log(n/2)+n
=cn log n-cn+n
≤cn log n(c≥1)严格来讲,数学归纳法还要求验证基础情况下要证明的结论也是成立的。但是对于n=1的基础情况,T(1)≤1 log 1并不成立。考虑渐近增长率的定义,我们只需要对于某个n0,证明对于n>n0,T(n)≤n log n即可。容易验证,对于n0=2,只需取c为任意充分大的常数,基础情况同样成立。
需要强调的是,在使用替换法的过程中,要证明的不等式必须形式上与归纳假设的不等式完全一样。对于上面的例子,我们的归纳假设是T(n)≤cn log n,则对n/2的情况使用归纳假设时,以及证明T(n)所满足的不等式时,我们均必须严格使用T(n)≤cn log n这一不等式,仅参数n可以作替换。
2.3.2 分治递归与递归树
分治算法的形式一般是将原始问题分解为若干小问题,每个小问题递归求解,再将小问题的解合并成原始问题的解。根据这一过程,分治递归具有如下形式:T(n)= a 划分为a个子问题Tnb划分后的子问题规模为原来的1/b+f(n)子问题划分与合并的代价其中,称f(n)为非递归代价(non-recursive cost)。“分治递归”的求解并不需要特殊的技巧,只需要将递归式逐步展开至基础情况,然后逐项把所有代价累加起来即可。只不过递归的层层展开会产生大量的中间结果,我们需要一个有力的工具清晰地整理、统计递归展开过程中所有的代价。这一工具就是下面介绍的递归树(recursion tree),如图2.2所示。
图2.2 T(n)=aTnb+f(n)的递归树
递归树的每个节点记录着递归的代价。我们仅记录非递归代价,这是因为仅非递归代价需要统计,递归代价被展开后记入下层子问题的代价。父节点到子节点的边表示递归求解的过程,递归树最底层的叶节点对应于递归的基础情况,它们的代价为O(1)。
递归树的第k层(所有深度为k的节点)对应于k次展开之后的递归式。例如,第0层就是未展开的原始递归式;第1层是递归式展开1次的情况,问题规模降到nb,总共有a 个子问题;第2层是递归式展开2次的情况,问题规模降到nb2,总共有a2个子问题;以此类推直至展开到最底层的叶节点对应于递归式的基础情况。根据递归式的展开方式,我们可以计算出递归树的高度为logbn,底层叶节点的个数为alogbn=nlogba。
2.3.3 Master定理
经过上面的准备,我们已经利用递归树这一工具,将递归式完全展开至基础情况。下面只需要基于递归树将所有代价求和即可解递归。我们以逐层求和(sum of row-sums)的方式来计算递归的代价。我们首先按照递归展开的规律计算每一层的和,这样每一层的和就组成一个logbn项的级数;然后再对每层的和组成的级数进行求和。
如果递归树每层的代价数列是一个等比级数,基于前面对于等比数列的分析(详见2.1.4节),以及函数渐近增长率的性质,我们可以得出递归树总代价的渐近增长率。具体而言,按照等比级数的公比大于1、等于1、小于1这3种情况,递归树总代价的渐近增长率也分3种情况。
●如果数列公比大于1(以根节点为第1项,叶节点为最后一项),则递归树的总代价就等于叶节点这一层的总代价,为alogbn=nlogba。
●如果数列公比等于1,则每一行的代价均为f(n)=nlogba,数列共有log n项,则递归树的总代价为nlogbalog n。
●如果数列公比小于1,则递归树的总代价等于根节点这一层的代价,为f(n)。
由于我们已经知道数列的第一项为f(n),最后一项为nlogba,所以只需要比较这两个函数的渐近增长率,则可以判断该等比数列的公比是上述哪种情况。基于上述分析,我们得出求解一般形式的“分治递归”的Master定理。
定理2.2 (Master定理) 令a、b为常数,且a≥1和b>1,f(n)为一定义于非负整数上的函数。T(n)为定义于非负整数上的递归函数:T(n)=aTnb+f(n)递归式中的nb指的是nb或者nb。
1) 如果存在某个常数ε>0,使得f(n)=O(nlogba-ε),则T(n)=Θ(nlogba)。
2) 如果f(n)=Θ(nlogba),则T(n)=Θ(nlogbalog n)。
3) 如果存在常数ε>0,使得f(n)=Ω(nlogba+ε),且存在某个常数c(c<1),使得对所有充分大的n,afnb≤cf(n),则T(n)=Θ(f(n))。
上述关于Master定理的讨论主要介绍了Master定理证明的基本原理,略去了其严格证明。Master定理的详细证明参见文献[1,2,3]。
在使用Master定理的过程中,我们需要注意nlogba和nlogba-ε的差别,无论常数ε取多小。例如,对于递归式:T(n)=2Tn2+n log n容易计算nlogba=n,则f(n)=n log n=Ω(nlogba)。但是仔细对照Master定理的要求我们发现,对于任意常数ε,n log n=Ω(n1+ε)均不成立。实际上对于任意常数ε我们有n log n=o(n1+ε)。所以这一递归式并不符合Master定理的第三种情况。深入辨析nlogba和nlogba-ε的差别使我们意识到Master定理的3种情况之间,还有很多情况未被覆盖。考察Master定理未能覆盖的情况对理解Master定理本身是很有帮助的,这一问题留作习题。

版权声明:如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:developerteam@list.alibaba-inc.com 进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:

华章出版社

官方博客
官网链接