2

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

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

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

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

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() 是否会因多次替换而存在缺陷，或者它是否以一种从中断处继续的方式实现？

4

1 回答 1

4

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

平均情况是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). 把它去掉，你就会得到另一个估计。

于 2021-02-11T22:59:39.157 回答