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)

这正确吗？

- cwbrd

---

你计算什么：墙上时间，操作次数？我怀疑将m个字符串连接起来的复杂度是二次的。 - user5547025

操作次数，例如分配一个长度为 n 的字符串应该需要 n 次操作。 - cwbrd

为什么分配长度为2m的字符串所需的时间是分配长度为m的字符串所需时间的两倍？ - user5547025

当然这取决于Python中字符串是如何实例化的，我考虑分配一个n个字符的数组，即使我实际上不知道它是如何完成的。 - cwbrd

@DisplayName: 因为每次需要将字符复制到新的字符串对象中，所以将10个字符连接到另外10个字符需要20个步骤才能生成新的字符串。如果在循环中执行此操作，则会出现二次行为。 - Martijn Pieters

@PadriacCunningham：请注意这里的连接是反向的；字符被放在前面。那篇文章中的优化不适用于此。这就是为什么我通常建议不要依赖它，因为很容易误解它的应用。 - Martijn Pieters

Answer 1

是的，在你的情况下^*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时避免创建新的字符串对象，但这种优化既脆弱又不可移植。由于您使用的是strB + strA（前置），因此该优化不适用。

- Martijn Pieters

---

把它们放在一个列表中可以避免二次时间复杂度，这绝对会优化性能。 - Martijn Pieters

通过我访问字符的方式（它们在字典树中），我必须反转我创建的列表，然后再进行连接，所以在我的情况下，我认为最好操作字符数组而不是字符串。谢谢你的建议。 - cwbrd

@Generalbrus：使用collections.deque，然后将项目添加到前面。 - Martijn Pieters

M个相同单词的追加趋势于M^2，每次迭代复制的字符数为：(M+M) + (2M+M) + (3M+M)+…(MM + M) = 2M + 3M + 4M + … + M^2 = M(1+2+3+…+M) = M * M(M+1)/2。因此，在Python中使用“+”连接长度为M的M个相同单词不应该是O(M^3)吗？ - karahbit

@karahbit：我不应该在循环中同时使用M表示字符数和追加次数。只有当单词长度等于追加次数时，复杂度才为O(M^3)，但这里并非如此。将追加文本的长度保持不变，因为它是一个固定值（平均追加长度），只需考虑追加次数即可。 - Martijn Pieters