JavaScript移除'b'与'ac'的时间复杂度解析求助

移除所有'b'的部分 #

result.replaceAll('b', '') 的时间复杂度是 O(n)，n是输入字符串的长度。replaceAll需要完整遍历一次字符串，找出所有'b'并替换，属于线性时间操作，这部分你判断的没错。

重点：移除'ac'的循环部分 #

这部分的复杂度容易搞混，咱们拆成两部分看：

单次replaceAll('ac', '')的耗时 #

每次调用replaceAll都要遍历当前字符串（长度记为k），找出所有非重叠的'ac'子串并替换，所以单次操作的时间是 O(k)，k是当前字符串的长度。

循环次数与总耗时 #

循环会一直执行，直到字符串里找不到'ac'为止。这里的关键是最坏情况：每次循环只能消掉一个'ac'，还会产生新的'ac'，导致循环次数和初始长度成正比。

举个极端例子：移除'b'后的字符串是"aa...accc...c"（比如m个'a'跟着m+1个'c'，总长度2m+1）。

• 第一次循环：长度2m+1，替换后变成(m-1)个'a'加m个'c'，长度2m-1
• 第二次循环：长度2m-1，替换后变成(m-2)个'a'加(m-1)个'c'，长度2m-3
• ...
• 第m次循环：长度3，替换后只剩1个'c'

把每次循环的耗时加起来：(2m+1)+(2m-1)+...+3+1 = (m+1)²。因为初始长度n'=2m+1（移除'b'后的长度），m约等于n'/2，所以总耗时是O((n')²)，而n'≤n，因此这部分最坏时间复杂度是O(n²)。

整体复杂度 #

把两部分合起来，整个函数的最坏时间复杂度是O(n²)，因为移除'ac'的循环在极端情况下会占主导。

空间复杂度是O(n)，因为JavaScript字符串不可变，每次替换都会生成新字符串，最多需要存储和原字符串长度相当的中间结果。

内容的提问来源于stack exchange，提问作者Gaurav