python - Python 中 str.replace 函数的大 O 表示法是什么？

Question

str.replace 的大 Oh 表示法是什么？ Python 中的函数？

它总是 O(n) 吗？

str = "this is string example"
print str.replace("is", "was")

thwas was string example

Answer 1

大 O 符号是在最坏情况下计算的，最坏情况下的 Python 源代码只是“找到 substr 的下一个位置，替换，然后走得更远”。一个替换执行 O(n) 操作(复制字符串)。一搜，根据http://effbot.org/zone/stringlib.htm ，在最坏的情况下执行 O(n*m) 操作。由于它最多可以替换 n/m，因此总的来说应该是令人惊讶的 O(n*n)。