Question

递归算法的时间复杂度

T(m,n) = T(m-1,n) + T(m,n-1)对于这样一个递归算法，其时间复杂度是多少呀？问题背景：在一个正方网格中，只能沿着网格往上走或者往右走，求原点到指定坐标中有多少条路径。为此设置一个递归函数，当指定坐标（m，n）中的m==0或者n==0时，函数值为1.除此之外的场合，等于其(m-1,n)和(m,n-1)路径之和。于是有T(m,n) = T(m-1,n) + T(m,n-1)递归算法。但是时间复杂度实在不会算，看了很多方法，但不知道用什么方法算。。。附：有人说是O[ (m+n) ^2 ]，我自己算是O[2 ^ (m+n) ]我的求解过程如图片所写...不知道正误...请教！

Answer 1

因为都是要遍历每一个节点，所以时空复杂度是一样的。 时间复杂度O(n); 空间复杂度O(n)； （n为节点数）