f*********g
发帖数: 110 | 1 leetcode 上Unique Paths, 我写了一个递归，但不是很明白这个递归的时间复杂度和
空间复杂度。我觉得空间复杂度是O(m*n),时间复杂度是O(m*n).不知道对不对，请大家
指点。
public int uniquePaths(int m, int n) {
if(m==1|| n==1) return 1;
return uniquePaths(m-1,n)+uniquePaths(m,n-1);
} | j*****y
发帖数: 1071 | 2 这个时间递归式子是
T(m, n) = T(m - 1, n) + T(m, n - 1)
可以用 substitution 证明 T(m, n) >= 2^(m + n)
【在 f*********g 的大作中提到】
: leetcode 上Unique Paths, 我写了一个递归，但不是很明白这个递归的时间复杂度和
: 空间复杂度。我觉得空间复杂度是O(m*n),时间复杂度是O(m*n).不知道对不对，请大家
: 指点。
: public int uniquePaths(int m, int n) {
: if(m==1|| n==1) return 1;
: return uniquePaths(m-1,n)+uniquePaths(m,n-1);
: }
| l****i
发帖数: 2772 | 3 T(m, n) <= 2^(m + n)吧
【在 j*****y 的大作中提到】
: 这个时间递归式子是
: T(m, n) = T(m - 1, n) + T(m, n - 1)
: 可以用 substitution 证明 T(m, n) >= 2^(m + n)
| w**********o
发帖数: 140 | | c********t
发帖数: 5706 | 5 同意，请空间复杂度是不是也是2^(m+n)，因为每次调用都要存m,n在stack里？
【在 l****i 的大作中提到】
: T(m, n) <= 2^(m + n)吧
|
|
