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

问题描述：

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

第一章的第三个问题要求你取一个字符串，例如

'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 中的字符串不是不可变的吗？如果我有一个字符串，并使用+运算符向其添加另一个字符串，它不会分配必要的空间、复制原始字符串，然后复制附加字符串吗？

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

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

或者O(n^2) 时间，对吗？还是我误解了 Python 处理附加的方式？

或者，如果你愿意教我如何钓鱼：我该如何自己找到答案？我尝试用 Google 搜索官方来源，但没有成功。我找到了https://wiki.python.org/moin/TimeComplexity，但这里没有任何关于字符串的内容。

解决方案 1：

在 CPython（Python 的标准实现）中，有一个实现细节通常使此操作复杂度为 O(n)，在字节码求值循环调用的代码中实现+，或+=使用两个字符串操作数。如果 Python 检测到左侧参数没有其他引用，它会调用realloc以尝试通过就地调整字符串大小来避免复制。您永远不应该依赖这一点，因为它是一个实现细节，并且如果realloc最终需要频繁移动字符串，性能无论如何都会降低到 O(n^2)。

如果没有奇怪的实现细节，由于涉及二次方的复制量，该算法的复杂度为 O(n^2)。这样的代码只有在具有可变字符串的语言（如 C++）中才有意义，即使在 C++ 中，您也希望使用+=。

解决方案 2：

作者依赖的优化恰好在这里，但并不明确可靠。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(1)`O(n)`

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

解决方案 3：

我在“Python Speed > 使用最佳算法和最快工具”上找到了这段文字：

字符串连接最好使用''.join(seq)which来完成O(n)。相反，使用'+'or'+='运算符可能会导致一个O(n^2)过程，因为可能会为每个中间步骤构建新的字符串。CPython 2.4 解释器在一定程度上缓解了这个问题；然而，''.join(seq)仍然是最佳实践

解决方案 4：

对于未来的访问者：由于这是一个 CTCI 问题，因此这里不需要任何有关学习urllib包的参考，特别是根据 OP 和书籍，这个问题是关于数组和字符串的。

这是一个更完整的解决方案，受到@njzk2 的伪启发：

text = 'Mr John Smith'#13 
special_str = '%20'
def URLify(text, text_len, special_str):
    url = [] 
    for i in range(text_len): # O(n)
        if text[i] == ' ': # n-s
            url.append(special_str) # append() is O(1)
        else:
            url.append(text[i]) # O(1)

    print(url)
    return ''.join(url) #O(n)


print(URLify(text, 13, '%20'))