Python中字符串连接的时间复杂度 [英] Time complexity of string concatenation in Python

问题描述

我正在分析我的代码的复杂性.从我在网上找到的，由于字符串在 python 中是不可变的，字符串和字符的连接应该是 O(len(string) + 1).

I'm analysing the complexity of my code. From what I found online, since strings are immutable in python, a concatenation of a string and a character should be O(len(string) + 1).

现在，这是我的一段代码(简化):

Now, here is my piece of code (simplified):

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) 时间.

Yes, in your case^*1 string concatenation requires all characters to be copied, this is a O(N+M) operation (where N and M are the sizes of the input strings). M appends of the same word will trend to O(M^2) time therefor.

您可以通过使用 str.join() 来避免这种二次行为:

You can avoid this quadratic behaviour by using str.join():

word = ''.join(list_of_words)

只需要 O(N)(其中 N 是输出的总长度).或者，如果您要重复单个字符，则可以使用:

which only takes O(N) (where N is the total length of the output). Or, if you are repeating a single character, you can use:

word = m * char

您正在添加字符，但首先构建一个列表，然后将其反转(或使用 collections.deque() 对象来获得 O(1) 前置行为)仍然是 O(n)复杂性，在这里轻松击败您的 O(N^2) 选择.

You are prepending characters, but building a list first, then reversing it (or using a collections.deque() object to get O(1) prepending behaviour) would still be O(n) complexity, easily beating your O(N^2) choice here.

^*1 从 Python 2.4 开始，CPython 实现避免在使用 strA += strB 或 strA = strA + strB，但这种优化既脆弱又不可移植.由于您使用 strA = strB + strA (前置)优化不适用.

^*1 As of Python 2.4, the CPython implementation avoids creating a new string object when using strA += strB or strA = strA + strB, but this optimisation is both fragile and not portable. Since you use strA = strB + strA (prepending) the optimisation doesn't apply.

这篇关于Python中字符串连接的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！