迭代字符串拼接的时间复杂度是 O(n^2) 还是 O(n)？

Question

我正在解决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中的字符串不可变，如果我有一个字符串并使用 + 操作符将另一个字符串添加到它中，它不会分配必要的空间，然后复制原始字符串并复制追加的字符串吗？

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

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

或者O(n^2) 时间，对吗？或者我对Python中的追加方式存在误解？

或者，如果您愿意教我钓鱼的技巧：我该如何自己找到答案？我尝试了在Google上查找官方来源，但一无所获。我找到了https://wiki.python.org/moin/TimeComplexity，但这没有关于字符串的内容。

- user5622964

---

有人应该告诉作者关于urllib.urlencode的事。 - wim

@wim 这道题目是为了练习数组和字符串而设置的。 - user5622964

本书的目的是教授面试问题，这些问题通常要求您重新发明轮子，以了解受访者的思考过程。 - James Wierzba

由于这是Python，我认为执行rtrim和replace会更受欢迎，并且在O(n)的范围内。复制字符串似乎是最低效的方法。 - OneCricketeer

@RNar，你能解释一下如何实现常数时间复制吗？ - James Wierzba

Answer 1

在Python的标准实现CPython中，有一个实现细节使得通常情况下这个操作的时间复杂度为O(n)，该实现细节实现在字节码评估循环调用+或+=时的代码中。如果Python检测到左参数没有其他引用，它会调用realloc来尝试通过原地调整字符串大小来避免拷贝。但是这不是你应该依赖的东西，因为它是一个实现细节，并且如果realloc需要频繁移动字符串，性能将降至O(n^2)。

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

- user2357112

---

我正在查看您提供的代码...看起来该代码的大部分是清理/删除指向被附加字符串的指针/引用，对吗？然后在末尾执行 _PyString_Resize(&v, new_len) 来为连接的字符串分配内存，然后 memcpy(PyString_AS_STRING(v) + v_len, PyString_AS_STRING(w), w_len); 进行复制。如果原地调整大小失败，则执行 PyString_Concat(&v, w);（我假设这意味着当原始字符串地址末尾的连续内存不可用时）。这如何显示加速？ - user5622964

@user5622964：哎呀，记错了奇怪的实现细节。没有有效的调整大小策略；它只是调用realloc并希望一切顺利。 - user2357112

将对象传递到memcpy中是否会给出该对象的地址或类似的东西？编辑：实际上这可能是有道理的，因为如果它返回地址，则添加长度是告诉它从v的末尾开始复制块。字符串在内存中是连续存储的吗？'PyString_Concat（＆v，w）;'是字符串“v”和“w”的完全重新复制吗？ - user5622964

这是指针算术。如果你想了解CPython源代码中奇怪的实现细节，就需要了解C语言。简单来说，PyString_AS_STRING(v)是第一个字符串数据的地址，加上v_len可以得到字符串数据结束后的地址。 - user2357112

不要在Java中尝试这个！ - wrschneider

Answer 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) 的，但这没关系，因为它在循环之外。

- njzk2

---

这个答案很好，因为它告诉了如何连接字符串。 - user877329

在计算运行时间的上下文中，精确的答案。 - ihaider

Answer 3

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

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

- OneCricketeer

Answer 4

对于未来的访客：由于这是一道CTCI问题，任何与学习urllib包有关的参考都不是必需的，特别是根据原帖和书籍，这个问题是关于数组和字符串的。

以下是一个更完整的解决方案，灵感来自于@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'))

- geekidharsh