"str.replace()"的时间复杂度或Big O表示法是什么?内置的JavaScript功能? [英] What is the time complexity or Big O notation for "str.replace()" built In function in Javascript?

问题描述

如果 str.replace()函数的时间复杂度是O(n)或O(1)，我会感到困惑，例如:

I am confused if the time complexity for str.replace() function is O(n) or O(1), for example:

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

答案是否总是相同?还是取决于我们要替换的内容?
有任何想法或有用的链接吗?！

Is it always the same answer or does it depend on what we replace?
Any thoughts or helpful links?!

推荐答案

绝对不是O(1)(比较字符串搜索算法)，但ECMAScript 6

It's definitely not O(1) (comparison of string searching algorithms) , but ECMAScript 6 doesn't dictate the search algorithm:

搜索字符串以查找searchString的第一个匹配项，并令pos为匹配的子字符串的第一个代码单元的字符串内的索引，而让match的字符串为searchString.如果未找到searchString，则返回字符串.

Search string for the first occurrence of searchString and let pos be the index within string of the first code unit of the matched substring and let matched be searchString. If no occurrences of searchString were found, return string.

所以这取决于实现方式.

So it depends on the implementation.

答案总是相同还是取决于我们要替换的内容?

Is it always the same answer or does it depend on what we replace?

通常，较长的搜索字符串会比较慢.与实施相关的速度要慢多少.

Generally, it will be slower for longer search strings. How much slower is implementation-dependent.

这篇关于"str.replace()"的时间复杂度或Big O表示法是什么?内置的JavaScript功能?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！