<分区>
我正在分析代码的复杂性。 根据我在网上找到的内容，由于字符串在 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)
这是正确的吗？
<分区>
我正在分析代码的复杂性。 根据我在网上找到的内容，由于字符串在 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)
这是正确的吗？
最佳答案
是的，在您的情况下，*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 (前置)优化不适用。
关于python - Python中字符串连接的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37133547/