这个时候的复杂性实际上是O（n ^ 2）吗？
我正在解决CTCI问题。
第一章的第三个问题是你拿一个string如
'Mr John Smith '
并要求您用%20replace中间空格：
'Mr%20John%20Smith'
作者在Python中提供了这个解决scheme，称之为O（n）：
def urlify(string, length): '''function replaces single spaces with %20 and removes trailing spaces''' counter = 0 output = '' for char in string: counter += 1 if counter > length: return output elif char == ' ': output = output + '%20' elif char != ' ': output = output + char return output
我的问题：
我知道这是O（n）从左到右扫描实际的string。 但是Python中的string是不可变的吗？ 如果我有一个string，我用+运算符添加另一个string，不是分配必要的空间，复制原来的，然后复制附加的string？
如果我有一个长度为1的nstring的集合，那么需要：
1 + 2 + 3 + 4 + 5 + ... + n = n(n+1)/2
或O（n ^ 2）时间，是吗？ 或者我误解了Python如何处理追加？
另外，如果你愿意教我如何钓鱼：我会如何去find自己的呢？ 我在尝试谷歌官方源代码方面一直没有成功。 我发现https://wiki.python.org/moin/TimeComplexity但这没有任何string。
在Python的标准实现CPython中，有一个实现细节，通常是O（n），在代码中由字节码评估循环对两个string操作数调用+或+=来实现 。 如果Python检测到左边的参数没有其他引用，它会调用realloc来通过调整string的大小来避免复制。 这不是你应该依赖的东西，因为它是一个实现细节，因为如果realloc最终需要经常移动string，无论如何性能会降低到O（n ^ 2）。
没有奇怪的实现细节，algorithm是O（n ^ 2）由于涉及二次复制量。 像这样的代码只能用可变string的语言才有意义，比如C ++，甚至在C ++中也要使用+= 。
作者依赖于在这里发生的优化，但不是明确可靠的。 strA = strB + strC通常是O(n) ，使得函数O(n^2) 。 但是，要确保整个过程是O(n) ，使用一个数组很容易：
output = [] # ... loop thing output.append('%20') # ... output.append(char) # ... return ''.join(output)
简而言之， append操作是分期付款 O(1) ，（尽pipe可以通过预先将数组分配到合适的大小来强化O(1) ），从而形成循环O(n) 。
然后join也是O(n) ，但没关系，因为它在循环之外。
我在Python中find了这段代码文本>使用最好的algorithm和最快的工具 ：
string连接最好用
''.join(seq)来完成，这是一个O(n)进程。 相反，使用'+'或'+='运算符可能会导致O(n^2)进程，因为可能会为每个中间步骤创build新的string。 CPython 2.4解释器有点缓解了这个问题; 然而，join''.join(seq)仍然是最好的做法
