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

Question

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

\n

我知道replace()是基于 Boyer\xe2\x80\x93Moore 算法，该算法在最坏情况下需要 O(n*m) 时间来查找子字符串，但这适用于单个子字符串吗？

\n

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

\n

当子字符串多次出现时该怎么办，如下例所示：

\n

old_string = '192.168.1.1'\nnew_string = old_string.replace('.', '|')\n

\n

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

\n

假设一个简单的循环需要 O(n)，例如：

\n

old_string = '192.168.1.1'\nnew_string = []\nfor ch in old_string:\n    new_string.append('|' if ch == '.' else ch)\n

\n

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

\n

内置的replace()对于多次替换是否存在缺陷，或者它的实现方式是从中断处继续吗？

\n

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). 把它去掉，你就得到了另一个估计。