Laufzeit Komplexität der Rekursion innerhalb Schleife mit Memoization

Question

Ich würde gerne wissen, wie die Zeit Komplexität für den folgenden Code zu bestimmen, mit Top-Down-dynamische Programmierung Ansatz mit Memo (beachten Sie, dass i, k, d kann ein beliebiger ganzzahliger Wert sein) :

solve(i, k, d) { 
    if (k >= d) { 
     A[i][k] = 0; 
     return 0; 
    } 

    if (i == 0) { 
     A[i][k] = 0; 
     return 0; 
    } 

    if (A[i][k] == null) { 
     for (int j = 0; j < k + 1; j++) { 
      A[i][k] = solve(i - 1, (k + 1 - j), d); 
     } 
    } 

    return A[i][k]; 
} 

Answer 1

Ausgabe:

solve(i - 1, (k + 1 - j), d) 

wird aus gebundenen Fehler geben, wenn j = 0 als A Index von 0 bis K [K wobei größten Index]

gehen sollte

---

ANTWORT: Die Funktion liefert O (n * n) Komplexität.

---

Intuition:

(es ist klar, dass der schlimmste Fall derjenige ist, wo keine Lösungen gibt, so konzentriere ich mich auf das)

Da der rekursiven Aufruf, bevor gemacht wird Wenn Sie Werte in den Memo-Cache schreiben, werden die letzten (kürzesten) Suffixe zuerst zwischengespeichert. Dies liegt daran, dass die Funktion zuerst mit einem Array der Länge N aufgerufen wird, das sich dann selbst mit einem Array der Länge N-1 aufruft, das dann ..., mit einem Array von len 0, das zwischengespeichert wird und zurückkehrt, dann das Array der Länge 1 wird zwischengespeichert und zurückgeliefert, ..., Länge N wird zwischengespeichert und zurückgeliefert.

Erläuterung:

Größe der Matrix Unter der Annahme, I x K und In Anbetracht schlimmsten Fall

[Anmerkung] Im schlimmsten Fall wird Funktionsaufruf von rechts unten der Matrix beginnt

A Initialisierung geschieht in zwei Fällen:

• i == 0

[Anmerkung] Im schlimmsten Fall k ist immer weniger, dass d.

For loop for `(I, K)` 
- Recursion call `for (i-1, k:[K to 0])` 
- Update value for `A[i, k]` 

[Anmerkung] i = 0 ist Basisfall, wenn die Funktion A initialisiert und 0 zurück