Von Ihrem Kommentar auf die Frage, so scheint es, dass die N Textzeichen erzeugt gleichmäßig zufällig sind. Für diese Einstellung beträgt die durchschnittliche Zeit der Brute-Force-Methode O (N - M), unabhängig davon, wie die Suchzeichenfolge generiert wird. (Man beachte, dass Wikipedia states O(N + M), aber wir können tatsächlich O (N - M) unter Verwendung der folgenden Analyse ableiten. Siehe auch these lecture notes).
Betrachten Sie die Iteration, in der die Suchzeichenfolge mit dem Text an Position i des Textes verglichen wird. Für jede Suchzeichenfolge hat jedes Zeichen der Suchzeichenfolge eine Wahrscheinlichkeit von p = 255/256, die nicht mit dem Zeichen der Suchzeichenfolge übereinstimmt. Sagen wir, dass ein "Erfolg" ist nicht passend. Dann ist die Anzahl der Versuche bis zum Erfolg ein Geometric Distribution mit expected (1 - p)/p = O(1) failures until success.
Also, für die Position i, die zu erwartenden Kosten ist O (1). Durch linearity of expectation, müssen wir jetzt über alle relevanten i summieren. Es gibt Θ (N - M) wie i.
Werden alle Buchstaben in Ihren Strings gleichmäßig zufällig generiert? Sind sie immer gleich lang? Wenn die Strings alternativ Worte einer natürlichen Sprache oder Daten sind, die von einem Prozess erzeugt werden, kann die Θ-Schätzung unterschiedlich sein. – anatolyg
Haben Sie sich auch die Erklärung in [Wikipedia] (https://en.wikipedia.org/wiki/String_searching_algorithm#Na.C3.AFve_string_search) angesehen? Wenn nicht, benutze das einfach. Wenn ja, geben Sie bitte an, was dort unklar ist. – anatolyg
Der zu suchende Text (N) wird zufällig generiert. Es hat ein Alphabet von 256 Zeichen (Byte-Puffer), – jdimko