"str.replace（）"のJavascriptでの組み込み関数の時間複雑さやBig O表記は何ですか？

Question

str.replace()機能のための時間の複雑さは、例えばO（N）またはO（1）である場合、私は混乱しています：

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

は、それが常に同じ答えであるか、それは我々が置き換えるものに依存していますか？
ご意見やご迷惑をおかけしますか？

Answer 1

まずそれは第二に、ストリング内のサブストリングを検索

が最も効率的であるKMPアルゴリズムを使用して線形時間で行うことができる

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

であるべきです。 ワーストケースで交換すると、リニアな時間もかかります。

だから、全体の時間の複雑さ：O（n）はここで

Nは、文字列strに依存しています。 最悪の場合、文字列全体を走査しても、replace関数に与えられたsearchValueが見つからないことになります。

Answer 2

それは間違いなくO（1）（comparison of string searching algorithms）はありませんが、ECMAScriptの6 doesn't dictate the search algorithm：

するsearchStringの最初の出現を検索する文字列とposがマッチしたの最初のコード単位の文字列内のインデックスでみましょう部分文字列と検索文字列を一致させます。 searchStringが見つからなかった場合は、文字列を返します。

したがって、実装によって異なります。

いつも同じ回答ですか、それとも私たちが置き換えるものに依存していますか？

一般的に、長い検索文字列の方が遅くなります。インプリメンテーション依存性はどれほど遅いか。

Answer 3

完全な回答については、実装の詳細を調べる必要があります。しかし、V8のruntime-strings.ccとbuiltins-string-gen.ccがあります。それは深いダイビングです - そして、私はC++を知らないので、正しいファイルを見ても私は完全にはわかりませんが、ニードルのサイズと深さによって異なるアプローチを使用しているようです検索ツリーを構築するために必要な再帰。

例えば、builtins-string-gen.ccにsearch_string 1の長さを有する場合、及びsubject_string長さ（0xFF）255よりも大きいかどうかをチェックES6 #sec-string.prototype.replace下のブロックがあります。これらの条件が真であればRuntime_StringReplaceOneCharWithStringのようになりますruntime-strings.ccが呼び出され、次にを最初にツリー移動可能なsubject_stringと呼ぶことを試みます。

この検索が再帰の制限に達すると、ランタイムはStringReplaceOneCharWithStringをもう一度呼び出しますが、今回はフラットなsubject_stringを呼び出します。

ここで私は部分的に教育された推測は、あなたはいつも何らかの線形時間を見ているということです。おそらくO（mn）の場合、再帰制限を守り、後続の素朴な検索を実行します。私はそれが素朴な検索であることを確かに知っていませんが、平らな文字列は、検索ツリーの代わりにsubject_stringのステップをたどることを意味します。

、おそらく何か未満O（MN）私は、彼らが再帰的subject_stringを歩いて集めているのか全くわからないけれども、ツリートラバーサルは、再帰制限をヒットしません。 Javascriptの実装のための時間の複雑さが何であるかを、実際のについては

、あなたはおそらく、直接ランタイム開発者に尋ねるか、彼らがやっていることは何時に実行する例を把握するために、他のstring searching algorithmsのようなものであるかどうかを確認したいと思います複雑。