Python中字符串连接的时间复杂度
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/37133547/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Time complexity of string concatenation in Python
提问by cwbrd
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).
我正在分析我的代码的复杂性。从我在网上找到的，由于字符串在 python 中是不可变的，字符串和字符的连接应该是 O(len(string) + 1)。
Now, here is my piece of code (simplified):
现在，这是我的一段代码（简化）：
word = ""
for i in range(m):
word = char_value + word
return word
The total time complexity should be:
总时间复杂度应该是：
(0+1) + (1+1) +...+ m = m(m+1)/2 = O(m^2)
(0+1) + (1+1) +...+ m = m(m+1)/2 = O(m^2)
Is this correct?
这样对吗？
回答by Martijn Pieters
Yes, in your case*1string 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.
是的，在您的情况下*1字符串连接需要复制所有字符，这是一个 O(N+M) 操作（其中 N 和 M 是输入字符串的大小）。因此，同一个词的 M 个附加将趋向于 O(M^2) 时间。
You can avoid this quadratic behaviour by using str.join():
您可以使用str.join()以下方法避免这种二次行为：
word = ''.join(list_of_words)
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:
只需要 O(N)（其中 N 是输出的总长度）。或者，如果您要重复单个字符，则可以使用：
word = m * char
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.
您正在添加字符，但首先构建一个列表，然后将其反转（或使用collections.deque()对象获得 O(1) 前置行为）仍然是 O(n) 复杂度，在这里很容易击败您的 O(N^2) 选择。
*1As of Python 2.4, the CPython implementation avoids creating a new string object when using strA += strBor strA = strA + strB, but this optimisation is both fragile and not portable. Since you use strA = strB + strA(prepending) the optimisation doesn't apply.
*1从 Python 2.4 开始，CPython 实现避免在使用strA += strBor时创建新的字符串对象strA = strA + strB，但这种优化既脆弱又不可移植。由于您使用strA = strB + strA（前置）优化不适用。
