Finde die größte palindromische Teilkette, Komplexität des Algorithmus

Question

Sie erhalten eine Zeichenfolge, z. "acdfdcqqc" und müssen einen Algorithmus erstellen, um den größten palindromischen Teilstring zu finden, in unserem Fall "cdfdc". Es ist einfach, eine O (n^2) Algorithmus, der durch Erstellen eines Arrays der Größe 2 N, und jedes Mal die Berechnung der Länge der größten Palindrom mit diesem Punkt für die Mitte dh ersinnen:

a - c - d - f - d - c - q - q - c 
1 0 1 0 1 0 5 0 1 0 1 0 1 4 1 0 1 

Für jede der 2n möglichen Start Punkte Ich bewege mich in beide Richtungen und finde die Länge des größten Palindroms, beginnend an dieser Position. Für jede der 2n-Operationen mache ich also höchstens O (n) -Operationen, daher die O (n^2) -Zeitkomplexität.

Ich weiß, dass es in linearer Zeit mit einem schickeren Algo getan werden kann: https://en.wikipedia.org/wiki/Longest_palindromic_substring.

Aber angenommen, dass die Zeichenfolge, die wir behandeln, aus natürlichem englischen Text extrahiert werden. Wenn wir eine Position zufällig in einem englischen Text auswählen, ist die erwartete Symmetrie, die wir erwarten könnten, ziemlich niedrig. Ich würde sogar sagen, dass die erwartete Symmetrie von weniger als einem Zeichen auf jeder Seite ist. Daher ist es in Ordnung für mich zu sagen, dass mein Algorithmus 2n mal konstante Operationen mit konstanter Zeit macht, wodurch der Algorithmus O (n) im Durchschnitt?

Answer 1

Die erwartete Laufzeit eines Algorithmus ist die durchschnittliche Laufzeit des Algorithmus über alle möglichen Eingaben. (Siehe Kapitel 5 von CLRS.) Wie das Lehrbuch zeigt, ist es nicht immer einfach, dies auszuarbeiten, und manchmal ist es nützlich, eine Alternative zu verwenden: die Laufzeit des Algorithmus für eine zufällig ausgewählte Eingabe. Aber das Prinzip ist das gleiche: Der Begriff "erwartete Laufzeit" ist probabilistisch, und gilt nur in Summe für eine große Anzahl von Anwendungen des Algorithmus.

Im Gegensatz dazu ist die "Worst-Case-Laufzeit" die schlechteste Laufzeit des Algorithmus bei jedem Eingang (jeder Länge). Das ist auch nicht immer einfach zu berechnen, aber es ist zugänglich für Berechnungen am oberen Rand, was im Falle der Groß-O-Notation gut ist, weil O (f (n)) nur sagt, dass f (n) ein oberer ist. gebunden.

Wenn Sie einen Algorithmus auf einen eingeschränkten Satz von Eingaben anwenden, können Sie über diesen eingeschränkten Satz entweder die erwartete oder die Worst-Case-Laufzeit angeben. Wenn die Eingaben nicht gleichmäßig über den Bereich der möglichen Eingaben verteilt sind, sollten Sie dies bei der Berechnung der erwarteten Laufzeit berücksichtigen. Wenn die Eingaben zufällig ausgewählte Teilstrings von englischem Text sind, ist die erwartete Länge des größten Palindroms (geringfügig) länger als die erwartete Länge des größten Palindroms eines zufällig ausgewählten Textes aus dem Fall von Palindromlänge das gesamte Universum von Zeichenfolgen, deren Zeichen aus dem Satz von Kleinbuchstaben und dem Leerzeichen stammen.Aber für beide dieser Sätze von Eingaben ist die erwartete Länge des längsten Palindroms O (1).

Es ist also gut zu sagen, dass Ihr Algorithmus "erwartet O (n)" ist, obwohl Sie auch die Art des Bereichs der Eingabezeichenfolgen angeben sollten. Wenn Sie jedoch die Eingabe für den Algorithmus nicht steuern können, ist auch die Worst-Case-Laufzeit relevant, da es für Ihren naiven Algorithmus leicht ist, eine Worst-Case-Eingabe zu erstellen, sodass ein DoS-Angriff eindeutig möglich ist.

Answer 2

Nr

In Algorithmus Design, zu sagen, dass ein Algorithmus in erwartet läuft O(n) Zeit bedeutet, dass es so für jede mögliche Eingabe tut. Das heißt, die Erwartung sollte sich auf die Zufälligkeit des Algorithmus (interne Münzwürfe) beziehen, nicht auf die Tatsache, dass die Eingabe gleichmäßig zufällig aus einer beschränkten Menge ausgewählt wird.

Es bedeutet jedoch nicht, dass Ihr Algorithmus nicht gut ist. Es ist in Ordnung, die Tatsache zu verwenden, dass die Eingabe auf englische Texte beschränkt ist und daher bestimmte Eigenschaften besitzt, die den Algorithmus schneller machen als bei allgemeinen Eingaben. Die von Ihnen verwendete Terminologie (erwartete O(n) Zeit) ist jedoch für Algorithmen reserviert, deren Laufzeit bei jedem Eingang O(n) ist.