数据结构:递归算法时间复杂度与空间复杂度计算方法
Ⅰ.递归算法求时间复杂度步骤
1.步骤
①先将这个递归算法分成两类,一类是满足递归条件时,一类为递归停止条件时
②然后分别算出这两类的执行次数。注意!如果在满足递归条件这一类中,计算执行次数的时候,发现要调用递归函数的话,就直接用函数记这一次的执行次数如3+T(n+1)
③根据题意,将变量从0开始的时候执行,一直执行到n,然后计算其执行次数
2.例题
计算下列递归算法的时间复杂度
分析:
①写出每一个分支语句所需要执行的次数
②将此递归算法分成两类,分别算执行次数。当为递归停止的条件时,即k=n-1,这一类的时间复杂度为n;当满足递归条件时,执行次数为(n-k)+T(n,k+1)
③计算当从n=0开始时,执行次数的变化。
解答:
第一步:
第二步:注意:一开始进入函数时k=0,所以第一次调用为T(n,0),然后k一直加,最后会达到k=n-1,所以最后时间的复杂度就为n的平方
易错点:
分支语句的话,算执行次数每次只能算其中一个语句的执行次数,不可以同时算两个分支语句
Ⅱ.递归算法求空间复杂度步骤
1.步骤
①先将这个递归算法分成两类,一类是满足递归条件时,一类为递归停止条件时
②然后分别算出这两类的空间占用度。注意:a.如果在满足递归条件这一类中,计算执行次数的时候,发现要调用递归函数的话,就直接用函数记这一次的执行次数如3+S(n+1) b.空间复杂度,只要你在函数体内定义了一个变量,那么就会占用一个空间
③根据题意,将变量从0开始的时候执行,一直执行到n,然后计算其执行次数
2.例题
计算下列递归算法的空间复杂度
分析:
①将此递归算法分成两类,分别算空间。当为递归停止的条件时,即k=n-1,这一类的空间复杂度为1,因为此时一共只调用了一次函数fun(),而一个fun()里面有一个空间;当满足递归条件时,执行次数为1+S(n,k+1)
②计算当从n=0开始时,空间复杂度的变化
解题:
第一步
第二步
另外
如果是非递归算法的空间与时间复杂度的计算,则不需要这么复杂,直接按照之前做的笔记的方法即可,笔记即在了纸质笔记本上