python - 迭代字符串追加的时间复杂度实际上是 O(n^2) 还是 O(n)？

Question

我正在解决 CTCI 的一个问题。

第一章第三题你有没有取一个字符串比如

'约翰·史密斯先生'

并要求您将中间空格替换为 %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 的标准实现 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++ 中你也想使用 +=。