str.replace（）的时间复杂度是否为O（n^2）？

Question

我试图找到python中内置的str.replace()的时间复杂性，这是我设法收集的数据（在这里和其他网站上）：

我知道replace()是基于Boyer–Moore算法的，最坏情况下需要O（n*m）的时间才能找到一个子串，但这是针对单个子串的吗

当replace()找到第一个子字符串并再次开始搜索时，是否返回“fixed”字符串的副本

当一个子串出现多个时，比如下面的例子：

old_string = '192.168.1.1'
new_string = old_string.replace('.', '|')

如果一次只能替换一个子串，那么对于单个子串，我们得到O（n*m），乘以子串的数量，最大n/m。这是O（n^2）

假设一个简单的循环需要O（n），比如：

old_string = '192.168.1.1'
new_string = []
for ch in old_string:
    new_string.append('|' if ch == '.' else ch)

这有意义吗？我错过什么了吗

对于多次替换，内置的replace（）是否有缺陷，或者它的实现方式是否可以继续它停止的地方

Answer 1

最坏的情况是O(n*(m1 + m2/m1))，其中n是字符串的长度，m1是搜索字符串的长度，m2是替换的长度

平均病例数为O(n * (1 + m2/m1))

原则上，算法如下所示：

initialize data structures.     # max time O(n)
while find next match:          # max time O(n*m1)
    copy unchanged string.      # max time O(n)
    copy replacement            # max time O((n/m1) * m2) + O(n)
copy rest of the string         # max time O(n)

有很多细节。（例如，他们必须管理内存，对于替换的大小与原始大小相同的情况，采取快速路径。）但下面是对每个步骤的解释，以及为什么需要这么长时间

1. 您正在初始化数据结构以获取结果。此初始化速度很快，但初始化时需要O(n)数据O(n)
2. 查找所有匹配项是最糟糕的情况，即对于向前比较m1-1个字符的每个字符，无法匹配最后一个字符，请备份并重试。因此，这可以是O(n*m1)
3. 复制O(n)数据需要O(n)时间
4. 最多可以有O(n/m1)个匹配项，我们为每个匹配项复制m2个数据。但是，我们也可以超出分配用于放入数据的大小。在这种情况下，我们必须创建一个新的位置来放置数据，复制我们所做的，然后继续。选择调整大小的阈值，以便总成本具有最大O(n)时间成本
5. 最后一次匹配后最多可以有O(n)个数据

把这些加在一起，把O(n)项吸收到O(n*m1)中，就得到了最初的估计值

回到一般情况，字符串搜索通常不会在返回前接近子字符串的末尾。大多数字母不匹配。大多数情况下，如果第一个字母匹配，则第二个字母不匹配。等等所以搜索通常是O(n)。把它去掉，你就得到了另一个估计