Komplexität der naiven Suche

Seien n Textlänge und m Musterlänge. Naive Suche ist $O(n m)$ im Worst Case (z.B. aaaa... vs aaa...b).

Durchschnittlich oft besser, aber ohne Garantie.

$$\textit{alignments} = n-m+1$$

Wo gebraucht

Erklärt, warum Log-Parsing und Virus-Signatur-Scans bei naiver Suche skalieren. Anlass für KMP/Boyer-Moore und für invertierte Indizes.

Vertiefung

Seien n die Textlänge und m die Musterlänge. Es gibt höchstens n minus m plus eins relevante Ausrichtungen. Pro Ausrichtung können bis zu m Zeichenprüfungen nötig sein, wenn der Unterschied erst spät sichtbar wird.

Die tatsächliche Arbeit hängt stark von den Daten ab. Häufige frühe Unterschiede machen die Suche praktisch günstig. Texte und Muster mit langen wiederholten Präfixen erzwingen dagegen an vielen Positionen fast vollständige Prüfungen. Die Analyse multipliziert daher Zahl der Ausrichtungen mit maximaler Arbeit je Ausrichtung.

Schwierigkeitsstufen

1. Zahl möglicher Startpositionen korrekt bestimmen.
2. Best- und ungünstige Eingabemuster unterscheiden.
3. Die Anzahl der Zeichenvergleiche für konkrete Wiederholungsmuster zählen.

Fallstricke

Die Laufzeit darf nicht allein mit der Textlänge begründet werden, wenn die Musterlänge variabel ist. Umgekehrt ist eine pessimistische Schranke keine Behauptung, dass jede reale Eingabe diese Arbeit verursacht.