再帰の時間複雑度を分析する方法

Question

再帰を使用して329:Given an integer matrix, find the length of the longest increasing path.というリートコードの問題が完了しましたが、時間の複雑さについてはわかりません。

時間の複雑さについては、最初に外側にループがあります。したがって、2つのループについては 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)

のようなもので、私は完全にこの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]; 
} 

Answer 1

findPathへの各呼び出しの後、cached[i][j]の内容は常に位置に1より大きいため、後続の呼び出しになります(i, j)う位置への再帰呼び出しにないリードその周りに。次に、各位置(i, j)がと最大4倍のと呼び出されます。これは、水平または垂直に隣接する位置への呼び出しによってのみアクセスされるため、最初の呼び出しでさらに再帰呼び出しが行われるためです。また、matrix[i][j] >= lastValueがでない場合の最悪の場合は、となります。したがって、上限はO(mn)です。m, nのサイズはmatrixです。