Zeitkomplexität und Raumkomplexität im rekursiven Algorithmus

Question

"The designer of an algorithm needs to balance between space complexity and time
complexity." - Comment on the validity of the statement in the context of recursive
algorithms.

Dies ist eine Frage aus dem vorherigen Papier meiner Universität. Aber ich konnte keine anständige Antwort finden. Eigentlich bin ich verwirrt darüber, wie ein Entwickler die Zeitkomplexität für jede rekursive Funktion minimieren kann. Ich verstehe das, wenn es eine gibt Schwanzrezision Dann kann die Raumkomplexität minimiert werden. Ich kann aber nicht die Idee der Zeitkomplexität bekommen.

Answer 1

Eines kommt in den Sinn Memoisierung. Einfach gut untersuchtes Problem dafür sind Fibonacci -Zahlen, einfache Rekursion lautet wie folgt:

fib(int n)
{
  if (n < 3)
    return 1;

  return fib(n-1) + fib(n-2);
}

Bei der Memoisierung können wir jedoch ein Hilfsarray verwenden, um zusätzliche Anrufe loszuwerden:

f[1]=f[2] = 1;
fib(int n)
{
  if (n < 3)
    return 1;

  if (f[n] == 0)
     f[n] = fib(n-1) + fib(n-2);

  return f[n];
}

Diese einfache Änderung verringert die Zeit von $ theta ( phi^n) $ bis $ theta (n) $.

Die Memoisierungstechnik verwendet manchmal mehr Gedächtnis, aber sehr schneller in der Zeit, und einer der Kompromisse, die Softwareentwickler sich darum kümmern sollte, ist dies.

Erläuterung der Memoisierung von Fibonacci -Zahlen:

Zuerst erstellen wir ein Array $ f $, um die bereits berechneten Werte zu speichern. Dies ist der Hauptteil aller Memoisierungsalgorithmen. Anstelle vieler wiederholter rekursiver Anrufe können wir die Ergebnisse speichern, die bereits durch frühere Schritte des Algorithmus erhalten wurden. Wie im Algorithmus gezeigt, setzen wir die $ f [1], f [2] $ bis $ 1 $.

In der ersten if Wir prüfen tatsächlich, ob wir uns am Anfang befinden oder nicht. Aber wir können das entfernen if Aussage. Aber um es einfacher zu lesen, habe ich es verlassen.

In dieser Sekunde if, wir prüfen, ob der Wert von fib(n) wird bereits berechnet oder nicht. Dies hindert uns von mehreren Aufrufen für dieselbe Zahl f(6), In normaler Rekursion haben wir den ersten Rekursionstaum, wie in der folgenden Abbildung und in der Memoisierungsversion den zweiten Baum gezeigt. Der Grund ist, dass wir bei der Memoisierung nur einmal die grünen Eckpunkte berechnen und dann in das Speicher (Array $ F $) speichern und bei Bedarf sie später abrufen.

In der folgenden Abbildung sind grüne Knoten Teile, die (auf diese Weise) berechnet werden müssen, gelbe Knoten vorberechnet und rote Knoten die Knoten sind wiederholt in der ersten Rekursion berechnet.

Wie aus dem Bild klar ist, haben wir im normalen Fall gerade vorberechtigt f(1) und f(2), Aber im Memoisierungsfall sind alle Funktionen für weniger als $ N-1 $ vorberechtigt, und dies führt zu exponentiell kleineren Rekursionsbaum. (In der Memoisierungszahl der roten Knoten ist Null, was in der normalen Rekursion exponentiell ist).