Нужна помощь в понимании временной сложности задачи Leetcode: самый длинный растущий путь в матрице ⇐ C++

[Anonymous]

Мне трудно понять временную сложность, указанную в leetcode для задачи «Самый длинный возрастающий путь в матрице», поэтому мое решение (показанное ниже) использует DFS с запоминанием, но в соответствии с редакционным решением упоминается, что временная сложность для этого подхода равна O(mn), где m — этоматрица.size(), а n — это матрица[0].size().
Точная формулировка
Time complexity : O(mn). Each vertex/cell will be calculated once and only once, and each edge will be visited once and only once. The total time complexity is then O(V+E). V is the total number of vertices and E is the total number of edges. In our problem, O(V)=O(mn), O(E)=O(4V)=O(mn).
но для решения этой проблемы нам нужно рассматривать все ячейки как начальную позицию и выполнять цикл, как показано ниже
for(int idx = 0; idx < matrix.size(); idx++){
for(int idy =0; idy < matrix[0].size(); idy++){
// WORK DONE IN longestIncreasingPathRec is definetly not O(1)
}
}

И цикл сам по себе равен O(mn), и работа, выполняемая в рекурсивном методе, мне не кажется O(1), и мне кажется, что в худшем случае должно быть O(mn) В этом случае общая временная сложность может составлять (O(mn)^2). Но опять же, я могу ошибаться, поэтому обращаюсь к нам, чтобы узнать, может ли кто-нибудь помочь прояснить, что мне здесь не хватает, или предоставить некоторые дополнительные ресурсы, которые могли бы помочь мне определить временную сложность в таких сценариях.
Обратите внимание, что в подходе № 1 к лит-коду просто используется DFS без запоминания, и упоминается, что временная сложность равна O(2^(m+n))
Time complexity : O(2^(m+n)). The search is repeated for each valid increasing path. In the worst case we can have O(2^(m+n)) calls.
Опять же, мне трудно понять, что мне кажется, что без запоминания каждая ячейка в худшем случае может повторяться mn раз, и в каждой ячейке у нас есть 4 варианта выбора (вверх, вниз, влево, вправо ), поэтому я не могу понять, как временная сложность получается O(2^(m+n)) без запоминания, поэтому, если кто-то сможет объяснить и это, это тоже будет здорово.
class Solution {
public:
vector dir = {{1,0}, {-1, 0}, {0, 1}, {0,-1}};

int longestIncreasingPath(vector& matrix) {
if(!matrix.size()){
return 0;
}
vector ans;
vector row(matrix[0].size(), 0);
vector cache(matrix.size(), row);
int longest = 0;
for(int idx = 0; idx < matrix.size(); idx++){
for(int idy =0; idy < matrix[0].size(); idy++){
int cand = longestIncreasingPathRec(matrix, cache, -1, idx, idy);
longest = max(cand, longest);
}
}

return longest;

}

int longestIncreasingPathRec(vector& matrix, vector& cache, int prevValue, int x, int y){

if(x < 0 || y < 0 || x >= matrix.size() || y >= matrix[0].size()){
return 0;
}

if(matrix[x][y] = matrix.size() || newY >= matrix[0].size()){
continue;
}

result = std::max(result, longestIncreasingPathRec(matrix, cache, matrix[x][y], newX, newY) + 1 );
}

cache[x][y] = result;
return result;
}
};


Подробнее здесь: https://stackoverflow.com/questions/793 ... increasing