本文主要是介绍【数据结构(邓俊辉)学习笔记】绪论03——递归分析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 意图
- 目标
- 1. 线性递归
- 数组求和
- 线性递归
- 减而治之
- 2. 递归分析
- 递归跟踪
- 递推方程
- 典型递推方程
- 3. 递归模式
- 多递归基
- 多向递归
- 4. 递归消除
- 空间成本
- 尾递归及其消除
- 5. 二分递归
- 分而治之
- 数组求和
- 6 . 效率
- 7. 算法设计优化总结
- 前n项计算算法
意图
数据结构中经常用到递归,递归分析和优化也是必要的,记录下递归分析
目标
- 理解不同递归形式(线性递归、二分递归和多分支递归等),如何选择应用以实现(遍历、分治等)算法策略。
- 利用递归跟踪和递推方程等方法分析递归算法的复杂度。
1. 线性递归
数组求和
//逐一取出每个元素,累加之
int sum ( int A[], int n ) { //数组求和算法(线性递归版)if ( 1 > n ) //平凡情况,递归基return 0; //直接(非递归式)计算else //一般情冴return sum ( A, n - 1 ) + A[n - 1]; //递归:前n - 1项求和,再累计第n - 1项
} //O(1)*递归深度 = O(1)*(n + 1) = O(n)
-
无论A[]内容如何,都有
T(n) = 1 + n*1 + 1 = n + 2 =O(n) = Ω(n) = Θ(n) -
递归必须得有个出口,不能无限递归
首先判断并处理n = 0之类的平凡情况,以免因无限递归而导致系统溢出。这类平凡情况统称“递归基”。平凡情况可能有多种,但至少要有一种(比如此处),且迟早必然会出现。
线性递归
算法sum()可能朝着更深一层进行自我调用,且每一递归实例对自身的调用至多一次。于是,每一层次上至多只有一个实例,且它们构成一个线性的次序关系。此类递归模式因而称作“线性递归”。
减而治之
线性递归的模式,往往对应于所谓减而治之的算法策略。
2. 递归分析
递归跟踪与递推方程分析递归算法时间和空间复杂度。
递归跟踪
递归跟踪可用以分析递归算法的总体运行时间与空间。
分析原则:
- 算法的每一递归实例都表示为一个方框,其中注明了该实例调用的参数
- 若实例M调用实例N,则在M与N对应的方框之间添加一条有向联线
递推方程
输入规模较为有限使用递归跟踪以图形化形式表现较为直观。当输入规模较大时,使用另一常用分析方法,即递推方程。
该方法无需绘出具体的调用过程,而是通过对递归模式的数学归纳,导出复杂度定界函数的递推方程(组)及其边界条件,从而将复杂度的分析,转化为递归方程(组)的求解。
书上有个求解思路,原话为:
在总体思路上,该方法与微分方程法颇为相似:很多复杂函数的显式表示通常不易直接获得,但是它们的微分形式却往往遵循某些相对简洁的规律,通过求解描述这些规律的一组微分方程,即可最终导出原函数的显式表示。微分方程的解通常并不唯一,除非给定足够多的边界条件。类似地,为使复杂度定界函数的递推方程能够给出确定的解,也需要给定某些边界条件。这类边界条件往往可以通过对递归基的分析而获得。
sum()算法递归方程求解
我试着从微分方程角度解释求解过程
T(n) = T(n - 1) + O(1) = T(n - 1) + c1, 其中c1为常数
T(0) = O(1) = c2, 其中c2为常数
微分方程角度看
Δ y Δ x \frac {\Delta y}{\Delta x} ΔxΔy = T ( n ) − T ( n − 1 ) n − ( n − 1 ) \frac {T(n) - T(n-1)}{n - (n- 1)} n−(n−1)T(n)−T(n−1) = c1
即 y ′ y' y′ = c1
y = c1x + c
因为 T(0) = O(1) = c2
所以 c = c2
即 y = c1x + c2
综上
T(n) = c1n + c2 = O(n)
空间复杂度
设采用该算法对长度为n的数组统计总和,所需空间量为S(n)
S(1) = O(1)
S(n) = S(n - 1) + O(1)
两式联合求解即得:
S(n) = O(n)
典型递推方程
3. 递归模式
多递归基
为保证有穷性,递归算法都必须设置递归基,且确保总能执行到。故同一算法的递归基可能(显式或隐式地)不止一个。
无论何种实现,均由如下reverse()函数作为统一的启动入口。
void reverse ( int*, int, int ); //重载的倒置算法原型
void reverse ( int* A, int n ) //数组倒置(算法的初始入口,调用的可能是reverse()的递归版或迭代版)
{ reverse ( A, 0, n - 1 ); } //由重载的入口启动递归或迭代算法
为得到整个数组的倒置,可以先对换其首、末元素,然后递归地倒置除这两个元素以外的部分。按照这一思路,通过递归跟踪可以证明,其时间复杂度为O(n)。
void reverse ( int* A, int lo, int hi ) { //数组倒置(多递归基递归版)if ( lo < hi ) {swap ( A[lo], A[hi] ); //交换A[lo]和A[hi]reverse ( A, lo + 1, hi - 1 ); //递归倒置A(lo, hi)} //else隐含了两种递归基 lo == hi lo > hi
} //O(hi - lo + 1)
算法复杂度
每递归深入一层,入口参数lo和hi之间的差距必然缩小2,因此递归深度(亦即时间复杂度)为:
(hi - lo) / 2 = n/2 = O(n)
多向递归
不仅递归基可能有多个,递归调用也可能有多种可供选择的分支。每一递归实例虽有多个可能的递归方向,但只能从中选择其一,故各层次上的递归实例依然构成一个线性次序关系,这种情况依然属于线性递归。
在数据结构(邓俊辉)学习笔记1-2—复杂度分析中求解幂函数 2 n 2^n 2n算法,复杂度是T( r) = O( 2 r 2^r 2r),这里使用递归实现。
我理解这样没计算一次,数据长度都会缩小一半
inline __int64 sqr ( __int64 a ) { return a * a; } //平方:若是连续执行,很快就会数值溢出!
__int64 power2 ( int n ) { //幂函数2^n算法(优化递归版),n >= 0if ( 0 == n ) return 1; //递归基;否则,视n的奇偶分别递归return ( n & 1 ) ? sqr ( power2 ( n >> 1 ) ) << 1 : sqr ( power2 ( n >> 1 ) );
} //O(logn) = O(r),r为输入指数n的比特位数
power2()算法的递归跟踪过程,如图所示。类似地也可看出,每递归深入一层,入口参数n即缩小一半,因此递归深度(亦即时间复杂度)应为
l o g 2 n log_2n log2n = O(logn)
将参数n所对应二进制展开的宽度记作r = logn,则由图看出,每递归深入一层,r都会减一,因此递归深度(亦即时间复杂度)应为:
O( r ) = O(logn)
复杂度由O( 2 r 2^r 2r)到O( r )
4. 递归消除
空间成本
递归算法所消耗的空间量主要取决于递归深度,故较之同一算法的迭代版,递归版往往需耗费更多空间,并进而影响实际的运行速度。引入一个结论
若每个递归实例仅需使用常数规模的空间,则递归算法所需的空间总量将线性正比于最大 的递归深度。
尾递归及其消除
在线性递归算法中,若递归调用在递归实例中恰好以最后一步操作的形式出现,则称作尾递归。属于尾递归形式的算法,均可以简捷地转换为等效的迭代版本。
reverse(A, lo, hi)算法为例
void reverse ( int* A, int lo, int hi ) { //数组倒置(规范整理之后的迭代版)while ( lo < hi ) //用while替换跳转标志和if,完全等效swap ( A[lo++], A[hi--] ); //交换A[lo]和A[hi],收缩待倒置区间
} //O(hi - lo + 1)
尾递归的判断应依据对算法实际执行过程的分析,而不仅仅是算法外在的语法形式。比如,递归语句出现在代码体的最后一行,并不见得就是尾递归;严格地说,只有当该算法(除平凡递归基外)任一实例都终止于这一递归调用时,才属于尾递归。
5. 二分递归
分而治之
将问题分解为若干规模更小的子问题,再通过递归机制分别求解。这种分解持续进行,直到子问题规模缩减至平凡情况。这也就是所谓的分而治之策略。
通常都是将原问题一分为二,故称作“二分递归”。
无论是分解为两个还是更大常数个子问题,对算法总体的渐进复杂度并无实质影响。
数组求和
新算法的思路是:
以居中的元素为界将数组一分为二;递归地对子数组分别求和;最后,子数组之和相加即为原数
组的总和。
int sum ( int A[], int lo, int hi ) { //数组求和算法(二分递归版,入口为sum(A, 0, n - 1))if ( lo == hi ) //如遇递归(区间长度已降至1),则return A[lo]; //直接返回该元素else { //否则(一般情况下lo < hi),则int mi = ( lo + hi ) >> 1; //以居中单元为界,将原区间一分为二return sum ( A, lo, mi ) + sum ( A, mi + 1, hi ); //递归对各子数组求和,然后合计}
} //O(hi - lo + 1),线性正比于区间的长度
算法启动后经连续m = l o g 2 n log_2n log2n次递归调用,数组区间的长度从最初的n首次缩减至1,并到达
第一个递归基。
刚到达任一递归基时,已执行的递归调用总是比递归返回多m = log2n次。其实换句话理解,若到达递归基,则执行了参数n的二进制位数 m = l o g 2 n m = log2n m=log2n次。
如上图,区间长度为8( l n g 2 8 lng_2 8 lng28 =3)当到达递归基时,调用堆栈看sum函数已经被调用3次。
到达区间长度为2^k的任一递归实例之前,已执行的递归调用总是比递归返回多m-k次。
如上图到达区间长度为2平方的实例,已执行的递归调用比返回多3-2=1次。
到达区间长度为2^k的任一递归实例之前,已执行的递归调用总是比递归返回多m-k次。
空间复杂度
鉴于每个递归实例仅需常数空间,故除数组本身所占的空间,该算法只需要O(m + 1) = O(logn)的附加空间。如上图所示区间长度为8,只需压栈3次。线性递归版sum()算法共需O(n)的附加空间,就这一点而言,新的二分递归版sum()算法有很大改进。
时间复杂度
与线性递归版sum()算法一样,此处每一递归实例中的非递归计算都只需要常数时间。递归实例共计2n - 1个,故新算法的运行时间为O(2n - 1) = O(n),与线性递归版相同。
6 . 效率
当然,并非所有问题都适宜于采用分治策略。实际上除了递归,此类算法的计算消耗主要来自两个方面。首先是子问题划分,即把原问题分解为形式相同、规模更小的多个子问题。
为使分治策略真正有效,不仅必须保证以上两方面的计算都能高效地实现,还必须保证子问题之间相互独立(各子问题可独立求解,而无需借助其它子问题的原始数据或中间结果)。否则,或者子问题之间必须传递数据,或者子问题之间需要相互调用,无论如何都会导致时间和空间复杂度的无谓增加。
7. 算法设计优化总结
前n项计算算法
这篇关于【数据结构(邓俊辉)学习笔记】绪论03——递归分析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!