Python中字符串+=操作为何未出现二次复杂度？实验解惑

你的原有认知确实是错误的——Python早已对字符串的+=操作做了针对性优化，并非每次都会复制整个字符串内容。

核心原因 #

Python从2.2版本开始，当字符串变量是当前作用域内的唯一引用时，解释器会直接在原字符串的内存空间末尾追加内容，而不是创建新字符串并复制原有内容。这种优化让res += "a"的均摊时间复杂度变为O(1)，整个foo函数的时间复杂度就是O(n)，所以执行时间会随iterations线性增长。

为什么foo2只快两倍 #

foo2使用列表append后join的方式，是一次性分配足够内存再完成所有字符串的拼接，理论上是最高效的字符串拼接方式。但foo的优化已经把复杂度降到了和foo2同级的线性，两者的差距仅来自于常数级的执行开销（比如列表操作的轻量性 vs 字符串扩展的底层操作），所以出现两倍左右的性能差是正常的。

验证方法 #

1. 跟踪字符串的内存地址（id()） #

修改foo函数，打印每次+=后的内存地址：

def foo(i):
    res = ""
    print(f"初始id: {id(res)}")
    for _ in range(5):
        res += "a"
        print(f"追加后id: {id(res)}")
    return res

foo(5)

如果输出的id始终不变，说明是在原对象上原地扩展，没有创建新字符串。

2. 查看引用计数（sys.getrefcount()） #

通过引用计数确认res是唯一引用：

import sys

def foo(i):
    res = ""
    for _ in range(3):
        print(f"当前引用数: {sys.getrefcount(res)}")
        res += "a"
    return res

foo(3)

输出的引用数通常是2（sys.getrefcount本身会增加一个临时引用），说明没有其他变量持有res的引用，解释器可以安全地进行原地扩展。

3. 破坏唯一引用，观察性能退化 #

如果给res增加额外引用，+=就会退化为全量复制：

import timeit

def foo(i):
    res = ""
    temp = res  # 增加一个额外引用
    for _ in range(i):
        res += "a"  
    return res

def foo2(i):
    res = []
    for _ in range(i):
        res.append("a")
    return "".join(res)

iterations = 10000
print(timeit.timeit('foo(iterations)', globals=globals(), number=100))
print(timeit.timeit('foo2(iterations)', globals=globals(), number=100))

此时foo的执行时间会远大于foo2，呈现明显的二次增长趋势，验证了没有优化时的性能表现。

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