Wie kann man die Speicher- und Zeitkomplexität eines Algorithmus bestimmen?

Das Bestimmen der Zeit- und Speicherkomplexität ergibt Zählen , wie viel von diesen beiden Ressourcen bei der Ausführung des Algorithmus verwendet wird und wie sich diese Beträge als Eingabegröße ändern ( k ) in diesem Fall) ändert sich.

Die Zeit hängt davon ab, wie oft jede der Anweisungen ausgewertet wird, und der Speicherplatz wird davon abhängen, wie groß die beteiligten Datenstrukturen sein müssen, um die Lösung berechnen zu können.

In diesem speziellen Szenario sehen Sie sich einen rekursiven Algorithmus an. Im Grunde genommen bedeutet das, 1) wie viele rekursive Aufrufe gemacht werden und 2) wie viel Arbeit für jeden dieser Aufrufe getan wird.

Da die Eingabe bei jedem Aufruf halbiert ist, sieht die Reihenfolge der Aufrufe etwa so aus:

Die Halbierung bei jedem rekursiven Aufruf führt zu einer logarithmischen Anzahl von Aufrufen.

Bei jedem Aufruf speichern wir eine konstante Anzahl von Variablen im Aufruf-Stack und machen eine konstante Menge an Arbeit (Operationen). Dies rührt von der Tatsache her, dass die Anzahl der Variablen und die Anzahl der Vergleiche / Additionen / Divisionen in jedem Aufruf nicht größer wird mit größerem k .

Die gesamte Zeitkomplexität ist die Anzahl der Anrufe multipliziert mit der Menge der Arbeit, die bei jedem Anruf geleistet wird, also

Für einige Konstanten A und B, die die tatsächlichen Zeitkosten eines rekursiven Aufrufs wiedergeben und Vergleiche bzw. Divisionen durchführen. Ähnlich:

Für geeignete Konstanten C und D für die Raumkosten der Rekursion bzw. des Variablenspeichers.

Bei dieser Art von Analyse geht es uns hauptsächlich um die asymptotische Komplexität, das heißt, wir interessieren uns nicht für die Konstanten, weil sie Details über die Maschine wiedergeben, die den Algorithmus ausführt, und wir wollen wirklich die Form von die Kurve (als k wird größer). Wenn Sie die Regeln für das Schreiben von Komplexität mit der Big-Oh-Notation befolgen, werden Sie das Ergebnis erhalten:

Bearbeiten: Details zur Speicherkomplexität

Wie bereits erwähnt, hängt die Speicherkomplexität davon ab, wie groß die Datenstrukturen sein müssen, um eine Lösung zu berechnen. Sie können also fragen: In dieser Funktion werden keine Datenstrukturen verwendet. Wo ist also das Protokoll (k)? Speicher gehen?

Die kurze Antwort: Sie müssen log(k) verschiedene Werte des Parameters k speichern, einen für jeden rekursiven Aufruf.

Die detaillierte Antwort: Es gibt eine implizite Datenstruktur, die hier vom Mechanismus des Funktionsaufrufs verwendet wird (den wir durch Rekursion ausnutzen) und ihr Name ist Aufrufliste . Jedes Mal, wenn sample(k) aufgerufen wird, wird ein neuer Stapelrahmen erstellt und eine Anzahl von Werten wird auf den Stapel geschoben: der lokale Wert des Parameters k , die Rückkehradresse und andere von der Implementierung abhängige Dinge. Auf diese Weise bildet jeder rekursive Aufruf eine "Schicht" auf dem Stapel, in der seine lokalen Informationen gespeichert sind. Das ganze Bild endet in etwa so:

(Ich habe hier den Anfangsparameterwert p von dem Wert von k bei jedem rekursiven Aufruf unterschieden, um Verwirrung zu vermeiden, hoffentlich)

Hauptsache, es gibt n = log(k) rekursive Aufrufe, es gibt n solche Stack-Frames. Jeder Stapelrahmen hat eine konstante Größe, und daher beträgt die Komplexität des Platzes O(log(k)) .

Sie betrachten log_2 (k), Logarithmus mit Basis 2 wirklich. Um Basen zu ändern, müssen Sie mit einer Konstante multiplizieren. Und da wir sowieso mit Konstanten multiplizieren, sind O (log (n)), O (ln (n)) und O (log_2 (n)) alle gleich.

Warum hat die obige Methode logarithmische Komplexität mit der Basis 2? Du teilst bei jedem Anruf k in die Hälfte. Wenn Sie rückwärts gehen, multiplizieren Sie bei jedem Anruf um 2. Multiplikation mit 2 ist 2 ^ n, und log_2 (n) ist genau das Gegenteil davon.

Vielleicht hilft es, wenn Sie einen Binärbaum zeichnen: Ein Baum mit n Knoten hat die Höhe log_2 (n), ein Baum mit der Höhe n hat 2 ^ n Knoten.