Python中字符串连接的时间复杂度

Question

我正在分析我的代码的复杂性。 从我在网上发现的情况来看，由于字符串在python中是不可变的，所以字符串和字符的连接应该是O（len（string）+1）。

现在，这是我的代码（简化版）：

word = ""
for i in range(m):
    word = char_value + word
return word

总时间复杂度应为：

（0+1）+（1+1）+…+m=m（m+1）/2=O（m^2）

这是对的吗？

Answer 1

是的，在您的情况下，字符串连接需要复制所有字符，这是一个O（N+M）操作（其中N和M是输入字符串的大小）。同一个单词的M个词尾将趋向于O（M^2）时间。

通过使用str.join()，可以避免这种二次行为：

word = ''.join(list_of_words)

只取O（N）（其中N是输出的总长度）。或者，如果要重复单个字符，可以使用：

word = m * char

您正在预处理字符，但是首先构建一个列表，然后反转它（或者使用collections.deque()对象来获得O（1）预处理行为）仍然是O（n）复杂度，很容易在这里击败您的O（n^2）选择。

---

^*1从Python 2.4开始，CPython实现在使用strA += strB或strA = strA + strB时避免创建新的字符串对象，但是这种优化既脆弱又不可移植。因为您使用strA = strB + strA（prepending），所以优化不适用。