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

Question

我正在解决 CTCI 的问题。

第一章的第三个问题是你取一个字符串如

'Mr John Smith '

并要求您将中介 spaces 替换为 %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 中的字符串不是不可变的吗？如果我有一个字符串并使用 + 运算符向其添加另一个字符串，它不会分配必要的 space，复制原始字符串，然后复制附加字符串吗？

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

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

或O(n^2)次，是吗？还是我弄错了 Python 如何处理追加？

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

Answer 1

在 CPython 中，Python 的标准实现，有一个实现细节使得这通常是 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++ 中您也想使用 +=.

Answer 2

我在 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 3

作者依赖于恰好在这里的优化，但不是明确可靠的。 strA = strB + strC 通常是 O(n)，使得函数 O(n^2)。但是，很容易确保整个过程是 O(n)，使用数组：

output = []
    # ... loop thing
    output.append('%20')
    # ...
    output.append(char)
# ...
return ''.join(output)

简而言之，append操作是amortizedO(1)，（虽然你可以通过预分配使其强大O(1)数组到正确的大小），使循环 O(n).

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

Answer 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'))

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

Is the time-complexity of iterative string append actually O(n^2), or O(n)?

python

string

algorithm

string-concatenation

time-complexity