请老师帮忙分析一下这个递归算法的时间复杂度
来源：2-5 递归算法的复杂度分析
时间流逝unity
2018-03-07
def climb(n, steps): count = 0 if n == 0: count = 1 elif n > 0: for step in steps: count += climb(n - step, steps) return count
走楼梯问题,10个台阶,每次只能走1~3步,n=10 steps = [1,2,3],这个算法是属于递归中只进行一次递归调用吗？
写回答
1回答
-
在这个算法中，递归调用是在一个for循环中的，for循环的次数是和step的长度相关的，steps的长度为3，所以这个函数内次三次调用了自己。
具体看时间复杂度，对于这三次调用，第一个参数分别是n-1，n-2和n-3。显然，取n-2和n-3的时候都将比n-1更快的到达递归底部，也就是用时更短。我们的算法复杂度是计算的上界，所以可以计算这三次调用都是n-1的情况的时间。我们的算法执行时间一定比这个时间短。即：
T(n) = T(n-1) + T(n-2) + T(n-3) < 3T(n-1)
我们只需要计算T(n) = 3T(n-1) 这样的递归调用的时间，结果就是以上算法时间的上界。
计算T(n) = 3T(n-1)的方式就和课程中讲的一样了。只不过此时，我们是看一棵完全三叉树有多少个节点？用等比数列求和公式：
3^0 + 3^1 + 3^2 + ... + 3^n = (3^n-1)/2 = O(3^n)
所以这个算法的时间复杂度是O(3^n)
012018-03-08
相似问题