How to analyze time complextity for recursiion

I complete a leetcode problem 329:Given an integer matrix, find the length of the longest increasing path. using recursion, and I am not sure about its time complexity.

For the time complexity, first there are for loops outside. Thus, it is T(m, n) = O(m*n) for the two loops. Inside the loop, there is a recursive calling findPath . It is like

T(m,n) = T(m-1, n)+T(m+1, n)+T(m, n-1)+T(m, n+1)

and I am completely lost for this one. Thanks if you can help explain this one for me.

Following is my code:

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];
} 

---

After each call to findPath , the content of cached[i][j] will always be greater than 1. Therefore subsequent calls to the position (i, j) will not lead to recursive calls to positions around it. We can then deduce that each position (i, j) is called a maximum of 4 times, as it can only be accessed by calls to positions either horizontally or vertically adjacent, only the first of which would lead onto further recursive calls. We also assume the worst case when matrix[i][j] >= lastValue is never satisfied. Therefore the upper bound is O(mn) , where m, n are the dimensions of matrix .

链接地址: http://www.djcxy.com/p/39340.html

上一篇: 我的功能的时间复杂度是多少？

下一篇: 如何分析递归的时间复杂性