Was ist die Zeit Komplexität oder Big O-Notation für "str.replace()" In Funktion in Javascript eingebaut?

Question

Ich bin verwirrt, wenn die Zeitkomplexität für str.replace() Funktion O (n) oder O (1), zum Beispiel:

var str = "Hello World"; 
str = str.replace("Hello", "Hi"); 
console.log(str); 
//===> str = "Hi World" 

Ist es immer die gleiche Antwort oder ist es hängt davon ab, was wir ersetzen?
Irgendwelche Gedanken oder hilfreiche Links ?!

Answer 1

Zum einen sollte es

str = str.replace("Hello", "Hi"); 

Zweitens sein,

eine Teil in einem String sucht, kann in linearer Zeit mit KMP-Algorithmus durchgeführt werden, welche die effizienteste ist. Ersetzen im schlimmsten Fall wird auch lineare Zeit dauern.

So Gesamtzeitkomplexität: O (n)

Hier n ist abhängig von der Zeichenfolge str. Im schlimmsten Fall wird es den gesamten String durchlaufen und immer noch nicht den searchValue finden, der der Replace-Funktion übergeben wird.

Answer 2

Es ist definitiv nicht O (1) (comparison of string searching algorithms), aber ECMAScript 6 doesn't dictate the search algorithm:

Suche String nach dem ersten Auftreten von searchString- und lasse po der Index innerhalb Zeichenfolge der ersten Codeeinheit des angepassten sein Teilstring und lassen Matched sein Suchstring. Wenn keine Vorkommen von searchString gefunden wurden, gebe einen String zurück.

Es hängt also von der Implementierung ab.

Ist es immer die gleiche Antwort oder hängt es davon ab, was wir ersetzen?

Im Allgemeinen wird es für längere Suchzeichenfolgen langsamer sein. Wie viel langsamer ist die Implementierung abhängig.

Answer 3

Sie müssen wirklich in Implementierungsdetails nach einer vollständigen Antwort suchen. Aber zu Beginn gibt es V8 runtime-strings.cc und builtins-string-gen.cc. Es ist ein tiefer Tauchgang - und ich kenne C++ nicht, also bin ich mir nicht ganz sicher, ob ich überhaupt die richtigen Dateien anschaue, aber sie scheinen je nach Größe der Nadel und Tiefe unterschiedlich zu sein Rekursion benötigt, um einen Suchbaum zu erstellen.

beispielsweise in builtins-string-gen.cc ein Block unter ES6 #sec-string.prototype.replace es, dass, wenn überprüft die search_string mit einer Länge von 1 hat, und wenn die subject_string Länge größer ist als 255 (0xFF). Wenn diese Bedingungen wahr sind, sieht es aus wie Runtime_StringReplaceOneCharWithString in runtime-strings.cc wird aufgerufen, die wiederum versuchen, StringReplaceOneCharWithString zuerst mit einem Baum-traversable subject_string aufrufen.

Wenn diese Suche das Rekursionslimit erreicht, führt die Laufzeitumgebung einen weiteren Aufruf an StringReplaceOneCharWithString, aber dieses Mal mit einem abgeflachten subject_string.

Also, meine teilweise begründete Vermutung hier ist, dass Sie immer eine Art linearer Zeit betrachten. Möglicherweise O (mn) wenn Sie das Rekursionslimit erreichen und eine naive Nachfolge-Suche durchführen. Ich weiß nicht sicher, dass es eine naive Suche ist, aber eine abgeflachte Zeichenfolge bedeutet für mich, dass ich Schritt für Schritt die subject_string statt durch einen Suchbaum durchquere.

Und möglicherweise etwas weniger als O (mn), wenn der Baum-Traversal nicht die Rekursion Grenze nicht getroffen, obwohl ich nicht ganz sicher bin, was sie gewinnen durch die subject_string rekursiv zu Fuß.

Für eine tatsächliche was die Zeitkomplexität Implementierungen für Javascript ist, werden Sie wahrscheinlich die Laufzeit Devs direkt oder sehen fragen, ob, was sie tun, wie andere string searching algorithms ist, um herauszufinden, welche Fälle in welcher Zeit laufen Komplexität.