相关疑难解决方法(0)

我正在研究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 …

我正在分析我的代码的复杂性.从我在网上找到的,因为字符串在python中是不可变的,字符串和字符的串联应该是O(len(string)+ 1).

现在,这是我的一段代码(简化):

word = ""
for i in range(m):
    word = char_value + word
return word

总时间复杂度应为:

(0 + 1)+(1 + 1)+ ... + m = m(m + 1)/ 2 = O(m ^ 2)

它是否正确？