迭代字符串追加的时间复杂度是O（n^2）还是O（n）？

Question

我正在研究CTCI之外的一个问题。

第1章的第三个问题是，你是否需要一个字符串，比如

'Mr John Smith '

并要求您用%20替换中间空格：

'Mr%20John%20Smith'

作者用Python提供了这个解决方案，称之为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）。但Python中的字符串不是不可变的吗？如果我有一个字符串，并且我使用+运算符向它添加另一个字符串，它不是分配了必要的空间，复制到原始字符串上，然后复制到附加字符串上吗？

如果我有一个长度为1的n字符串的集合，则需要：

1 + 2 + 3 + 4 + 5 + ... + n = n(n+1)/2

或O（n^2）时间，是吗？或者我是不是搞错了Python是如何处理追加的？

或者，如果你愿意教我如何钓鱼：我该如何为自己找到答案？我试图用谷歌搜索官方消息来源，但一直没有成功。我找到了https://wiki.python.org/moin/TimeComplexity但是这个没有任何字符串。

Answer 1

我在Python Speed > Use the best algorithms and fastest tools上找到了这段文字：

String concatenation is best done with ''.join(seq) which is an O(n) process. In contrast, using the '+' or '+=' operators can result in an O(n^2) process because new strings may be built for each intermediate step. The CPython 2.4 interpreter mitigates this issue somewhat; however, ''.join(seq) remains the best practice

Answer 2

在Python的标准实现CPython中，有一个实现细节使其通常为O（n），用the code the bytecode evaluation loop calls for ^{} or ^{} with two string operands实现。如果Python检测到左参数没有其他引用，它将调用realloc来尝试通过调整字符串的大小来避免复制。这不是您应该依赖的东西，因为这是一个实现细节，并且因为如果realloc最终需要频繁移动字符串，性能无论如何都会降低到O（n^2）。

如果没有奇怪的实现细节，算法是O（n^2），因为涉及到二次复制量。这样的代码只在一种具有可变字符串的语言中是有意义的，比如C++，甚至在C++中，你也希望使用^ {CD2}}。

Answer 3

作者所依赖的优化恰好在这里，但并不明确可靠。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)（尽管可以通过将数组预分配到正确的大小使其变得强大），从而使循环O(n)。

然后join也是O(n)，但这没关系，因为它在循环之外。