我正在处理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中的字符串不是一成不变的吗？如果我有一个字符串，并且用+运算符向它添加了另一个字符串，它是否分配了必要的空间，复制了原始字符串，然后复制了追加字符串？

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

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

还是 O（n ^ 2）时间 ，是吗？还是我在Python处理附加方式方面弄错了？

或者，如果您愿意教我如何钓鱼：我将如何亲自找到答案？我尝试向Google寻求官方消息一直没有成功。我发现https://wiki.python.org/moin/TimeComplexity，但这在字符串上没有任何内容。