python - str.replace() 的时间复杂度是否为 O(n^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() 是否会因多次替换而存在缺陷,或者它是否以一种从中断处继续的方式实现?
解决方案
最坏的情况是字符串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)
. 把它去掉,你就会得到另一个估计。
推荐阅读
- c# - 解析字节数组的最快方法?
- sql-server - 查找为事实表中的每个键组合创建和更新的记录数
- c++ - Gtest:跨多个测试全局访问自动变量
- java - 在 java 的 mongo 聚合查询中使用“提示”的语法
- r - parLapply 在代码内部和外部花费完全不同的时间
- javascript - 查找数组中最长的字符串
- c++ - 如何在5之前设置没有值的宽度
- php - 如何同时使用xammp和mysql服务器
- c# - 确定正在使用的语言 aspx 文件
- corda - 运行打开附件ID:5E14F03C543953911C985450FC3B120DB262DCA60961B02D8B8311D039D4FDE2