Warum beträgt die Zeitkomplexität für den längsten zunehmenden Pfad in einer Matrix O(nm)? ⇐ C++

[Guest]

Es fällt mir schwer, die zeitliche Komplexität für die Lösung des folgenden LeetCode-Problems 329 zu verstehen. Längster zunehmender Pfad in einer Matrix:

Gegeben an m x n Ganzzahlmatrix, gib die Länge des längsten ansteigenden Pfads in der Matrix zurück.
Aus jeder Zelle, Sie kann sich entweder in vier Richtungen bewegen: links, rechts, oben oder runter. Sie dürfen sich nicht diagonal oder außerhalb der Grenze bewegen (d. h. ein Umlauf ist nicht zulässig).

Meine Lösung verwendet DFS mit Speicherung:

Code: Select all

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

Im LeetCode-Editorial heißt es, dass die Zeitkomplexität für diesen Ansatz O(mn) beträgt, wobei m Matrix.size() ist und n Matrix[0].size() ist. :

Zeitkomplexität: O(mn). Jeder Scheitelpunkt/jede Zelle wird einmal und nur einmal berechnet und jede Kante wird einmal und nur einmal besucht. Die gesamte Zeitkomplexität beträgt dann O(V+E). V ist die Gesamtzahl der Eckpunkte und E ist die Gesamtzahl der Kanten. In unserem Problem ist O(V)=O(mn), O(E)=O(4V)=O(mn).

Problem< /h2>
Ich bezweifle die obige Aussage, denn um das Problem zu lösen, müssen wir alle Zellen als Startposition betrachten und wie unten gezeigt eine Schleife durchführen:

Code: Select all

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)
}
}

Die Schleife selbst ist O(mn) und die in der rekursiven Methode geleistete Arbeit scheint mir nicht O(1) zu sein, und ich habe das Gefühl, dass sie im schlimmsten Fall O(mn) sein sollte daher könnte die Gesamtzeitkomplexität O(mn)^2 betragen. Warum ist es O(nm) und nicht O(mn)^2?
Was fehlt mir hier? Wie kann hier die richtige Zeitkomplexität ermittelt werden?
LeetCode spricht auch von „Ansatz Nr. 1“, bei dem nur DFS ohne Auswendiglernen verwendet wird, und es wird erwähnt, dass die Zeitkomplexität O(2^) beträgt (m+n)):

Zeitkomplexität: O(2^(m+n)). Die Suche wird für jeden gültigen ansteigenden Pfad wiederholt. Im schlimmsten Fall können wir O(2^(m+n))-Aufrufe haben.

Auch hier fällt es mir schwer, das zu verstehen . Für mich kommt es so vor, als ob jede Zelle ohne Auswendiglernen im schlimmsten Fall mn-mal rekursiv sein kann und wir in jeder Zelle 4 Möglichkeiten haben (oben, unten, links, rechts). Warum ergibt sich also die Zeitkomplexität als O(2^(m+ n))?
Hinweis: Ich habe meine Bitte um Klarstellung auch im LeetCode-Forum gepostet und andere Kommentare zu dieser Frage durchgesehen. Ich habe viele Fragen zur zeitlichen Komplexität dieser Ansätze gefunden, aber kaum Antworten erhalten. Wo es Antworten gab, wurde nicht klargestellt, wonach ich suche, daher habe ich beschlossen, meine Frage hier zu posten.