我很困惑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)
这里n依赖于字符串str。在最坏的情况下，它将遍历整个字符串，但仍然找不到给定给replace函数的searchValue。
这绝对不是O(1)(字符串搜索算法的比较)，但ECMAScript 6没有规定搜索算法：
在字符串中搜索searchString的第一次出现，并让pos是匹配子字符串的第一个代码单元的字符串中的索引，并让match是searchString。如果未找到searchString，则返回字符串。
所以这取决于实现。
它总是相同的答案还是取决于我们替换了什么？
通常，搜索字符串越长，速度越慢。速度慢多少取决于实现。
您必须仔细研究实现细节才能得到完整的答案。但首先有V8的runtime-strings.cc和内置的string-gen.cc。这是一个深入的研究——我不知道c++，所以我甚至不完全确定我是否在寻找正确的文件，但它们似乎使用了不同的方法，这取决于指针的大小和构建搜索树所需的递归深度。
例如，在内置字符串生成.cc中，ES6 #sec-string.prototype.replace下有一个块，用于检查search_string的长度是否为1，以及subject_string的长度是否大于255(0xFF)。当这些条件为真时，它看起来像是运行时字符串中的Runtime_StringReplaceOneCharWithString。调用cc，它将首先尝试使用可遍历的树subject_string调用StringReplaceOneCharWithString。
如果搜索达到递归限制，运行时将再次调用StringReplaceOneCharWithString，但这次调用的是扁平的subject_string。
所以，我有部分依据的猜测是，你总是在看某种线性时间。当达到递归极限并进行后续天真搜索时，可能O(mn)。我不确定这是否是一个天真的搜索，但对我来说，一个扁平的字符串意味着逐步遍历subject_string，而不是通过搜索树。
当树遍历没有达到递归极限时，可能会小于O(mn)，尽管我不完全确定他们通过递归遍历subject_string得到了什么。
对于实际的，Javascript实现的时间复杂性是什么，您可能想直接询问运行时开发人员，或者看看他们所做的是否像其他字符串搜索算法一样，以了解哪些情况在什么时间复杂性下运行。