Javascript 中内置函数“str.replace()”的时间复杂度或 Big O 表示法是多少？

我很困惑如果时间复杂度str.replace()函数的复杂度为 O(n) 或 O(1)，例如：

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

它总是相同的答案还是取决于我们替换的内容？
有什么想法或有用的链接吗？

首先应该是

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

第二，

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

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

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