Javascript 中内置函数的“str.replace()”的时间复杂度或大 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

首先应该是

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

第二，

使用 KMP 算法可以在线性时间内搜索字符串内的子字符串，这是最有效的。在最坏的情况下更换也将花费线性时间。

所以总体时间复杂度：O(n)

这里n取决于字符串str。在最坏的情况下，它最终会遍历整个字符串，但仍然找不到提供给替换函数的 searchValue。

Answer 2

它绝对不是 O(1) （字符串搜索算法的比较），但 ECMAScript 6没有规定搜索算法：

搜索字符串中首次出现的 searchString，并令 pos 为匹配子字符串的第一个代码单元在字符串中的索引，并令匹配为 searchString。如果未找到 searchString，则返回字符串。

所以这取决于实施。

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

一般来说，搜索字符串越长，速度会越慢。慢多少取决于实现。