我正在分析我的代码的复杂性.从我在网上找到的,由于字符串在 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中字符串连接的时间复杂度
发布评论