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

是的,在你的情况下^*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(预先),优化不适用.