如何分析递归的时间复杂性
我完成了一个leetcode问题329：给定一个整数矩阵，找出最长增长路径的长度。 使用递归，我不确定它的时间复杂性。
对于时间复杂性，首先是外部循环。 因此，两个回路的T(m, n) = O(m*n) 。 在循环内部，有一个递归调用findPath 。 它像是
T(m,n) = T(m-1, n)+T(m+1, n)+T(m, n-1)+T(m, n+1)
我完全失去了这一个。 谢谢，如果你能帮我解释一下这个。
以下是我的代码：
int longestIncreasingPath(vector<vector<int>>& matrix) {
if (matrix.size() == 0 || matrix[0].size() == 0) return 0;
vector<vector<int>> cached(matrix.size(), vector<int>(matrix[0].size(), 0));
int maxVal =0;
for(int i=0; i<matrix.size(); i++){
for(int j=0; j<matrix[0].size();j++){
int length = findPath(matrix, i, j , cached, INT_MAX);
maxVal=max(length, maxVal);
}
}
return maxVal;
}
int findPath(vector<vector<int>>& matrix, int i, int j,
vector<vector<int>>& cached, int lastValue){
if(i<0 || j<0 || i>=matrix.size() || j>=matrix[0].size() || matrix[i][j]>=lastValue){
return 0;
}
if(cached[i][j]==0) {
int current = matrix[i][j];
int temp = 0;
temp= max(temp, findPath(matrix, i-1, j, cached, current));
temp= max(temp, findPath(matrix, i+1, j, cached, current));
temp= max(temp, findPath(matrix, i, j-1, cached, current));
temp= max(temp, findPath(matrix, i, j+1, cached, current));
cached[i][j] = temp+1;
}
return cached[i][j];
}
每次调用findPath ， cached[i][j]将始终大于1.因此，后续对位置(i, j)调用将不会导致对其周围位置的递归调用。 然后我们可以推断每个位置(i, j)最多称为4次，因为它只能通过调用水平或垂直相邻的位置来访问，只有第一个位置会导致进一步的递归调用。 当matrix[i][j] >= lastValue永远不会被满足时，我们也假设最坏的情况。 因此，上界是O(mn) ，其中m, n是matrix的维数。