Ich habe diesen Artikel Ein großes Interview-Problem zurückgezogen , der Autor kam mit einem work break Problem und gab drei Lösungen. Der effiziente Algorithmus verwendet den memoization -Algorithmus und der Autor sagt, dass die Zeitkomplexität im schlimmsten Fall O(n^2) seit the key insight is that SegmentString is only called on suffixes of the original input string, and that there are only O(n) suffixes ist.
Allerdings fällt es mir schwer zu verstehen, warum es O(n^2) ist. Könnte mir bitte jemand einen Hinweis oder einen Beweis geben?
Der Memo-Algorithmus von Abschied von einem großen Interview-Problem
%Vor%Intuition
(Es ist klar, dass der schlimmste Fall derjenige ist, wo es keine Lösungen gibt, also konzentriere ich mich darauf)
Da der rekursive Aufruf vor dem Einfügen von Werten in den Memo-Cache erfolgt, werden die letzten (kürzesten) Suffixe zuerst zwischengespeichert. Dies liegt daran, dass die Funktion zuerst mit einer Zeichenkette der Länge N aufgerufen wird, die sich dann mit einer Zeichenkette der Länge N-1 aufruft, die dann ...., mit einer Zeichenkette von len 0, die zwischengespeichert wird und dann zurückgibt Die Zeichenfolge der Länge 1 wird zwischengespeichert und gibt zurück, ..., die Länge N wird zwischengespeichert und zurückgegeben.
Wie der Hinweis andeutet, werden nur Suffixe zwischengespeichert und es gibt nur N davon. Dies bedeutet, dass zu dem Zeitpunkt, zu dem die Top-Level-Funktion das Ergebnis ihres ersten rekursiven Aufrufs erhält (dh auf einem Suffix der Länge N-1), der Cache bereits mit den N-1-Suffixen gefüllt ist.
Nehmen wir nun an, dass die N-1 letzten Suffixe bereits zwischengespeichert sind, muss die for-Schleife N-1 rekursive Aufrufe machen, die jeweils O (1) nehmen (da die Antwort bereits zwischengespeichert ist), was O (N) ergibt. Der (Vor-) Aufbau des Cachespeichers des letzten N-1 erfordert jedoch O (N ^ 2) (wie nachstehend erläutert), wobei O (N) + O (N ^ 2) = O (N ^ 2) gilt. p>
Beweis durch mathematische Induktion
Diese Erklärung kann leicht in einen formalen Beweis mit Induktion übersetzt werden. Hier ist der Kern davon:
( f(N) ist die Anzahl der Operationen, die für die Ausführung der Funktion bei einer Eingabe der Länge N benötigt werden)
Induktionshypothese - es existiert eine Konstante c s.t. %Code%.
Der Basisfall ist trivial - für eine Zeichenfolge der Länge 1 können Sie eine Konstante f(N) < c*N^2 finden, so dass c
Induktionsschritt
Wiederholung der Reihenfolge der Dinge passieren:
Schritt 1: Die Funktion ruft sich als erstes das Suffix der Länge N-1 auf und erstellt einen Cache, der die Antwort für die letzten N-1 Suffixe enthält
Schritt 2: Die Funktion ruft sich dann selbst öfter O (N) auf, wobei jeder O (1) nimmt (dank diesem Test: f(1) < c*N^2 = c , und die Tatsache, dass der Cache bereits in gefüllt ist. Schritt 1 ).
So bekommen wir:
%Vor% Also haben wir if (memoized.containsKey(input)) , was den Beweis vervollständigt.
Zunächst können wir für eine gegebene Zeichenfolge mit der Länge N in N * (N-1) / 2 Segmente aufbrechen und prüfen, ob jedes Segment im Wörterbuch enthalten ist. Diese Kosten sind O (N ^ 2)
Komm zurück zu deinem Code, beginne mit der Zeichenkette N, wir teilen sie in zwei kleinere Strings, Länge 'a' , und 'N - a' . Und für jede Unterzeichenfolge (oder Präfix) beginnen wir von 0 und enden bei 'a' , wir überprüfen es nur einmal!
Von jedem Segment N - a überprüft es auch jedes seiner Präfix einmal und speichert es in die gespeicherte Tabelle , so wird dieser Schritt sicherstellen, dass das nächste Mal, wenn wir das gleiche gemacht haben Bewegen, teilen Sie die Zeichenfolge an dieser Stelle, wir müssen das Ergebnis nur ohne weitere Arbeit zurückgeben (unter der Annahme, dass eine Karte das Ergebnis für eine bestimmte Zeichenfolge in O (1) abrufen und zurückgeben wird). Dieser Speicher- und Wiederherstellungsschritt stellt auch sicher, dass die Eroberung und Teilung nur einmal durchgeführt wird.
Nach dem ersten und zweiten Punkt kommen wir zu dem Schluss, dass nur einmal (N - 1) / 2-Segmente zu untersucht werden, was zu der Tatsache führt, dass die Kosten ist O (N ^ 2)
Hinweis : Nur mit der Annahme für Kosten für beide dict.contains(input) und memoized.containsKey(input) sind O (1) < so ist die Komplexität O (N ^ 2).
Wenn die Eingabe die Länge N hat, wäre die maximale Anzahl der Wörter, die das Wörterbuch enthalten könnte, N. Daher müssen Sie alle verschiedenen Kombinationen der Länge 1..N überprüfen. was ist N (N-1) / 2
nehmen Sie eine Eingabekette von, aaaaa
gibt es N x 'a' Strings
N-1 'aa' Zeichenfolgen
und so weiter
Tags und Links algorithm recursion time-complexity memoization