str.replace() 的时间复杂度是 O(n^2) 吗？

Question

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

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

replace() return 找到第一个子字符串然后再次开始搜索时是否复制“固定”字符串？

当我们有多个次出现的子字符串时，如以下示例：

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)

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

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

将这些相加并将 O(n) 项吸收到 O(n*m1) 中，您将得到原始估计值。

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

str.replace() 的时间复杂度是 O(n^2) 吗？

Does str.replace() have a time complexity O(n^2)?

python

algorithm

replace

time-complexity

boyer-moore