Python中字符串拼接函数的时间复杂度及O(n+m)合理性咨询

先看你给出的函数代码：

def concat_strings(string1, string2):
    return string1 + " " + string2

这个函数的时间复杂度确实是O(n + m)，其中n为string1的长度，m为string2的长度。

原因很直接：Python中的字符串是不可变类型，每次用+拼接字符串时，都需要创建新的字符串对象，并把原有字符串的所有字符复制到新内存空间中。这里的string1 + " " + string2会分两步执行：

• 第一步：把string1和空格拼接，需要复制n + 1个字符；
• 第二步：把第一步得到的临时字符串和string2拼接，需要复制(n + 1) + m个字符。

总的字符复制操作次数是(n+1) + (n+1+m)，化简后是2n + m + 2，忽略常数项和低阶项，时间复杂度就是O(n + m)。

内容的提问来源于stack exchange，提问作者user19245296