string += "a" 和 string = string + "a" 的时间复杂度一样吗？

Question

在这两个语句中，我都将一个字符附加"a"到字符串中s：

1. s += "a"
2. s = s + "a"

Python 中哪个语句的时间复杂度更好？

Answer 1

它们具有相同的时间复杂度。

\n

在一般 Python 标准定义的情况下：它们都具有相同的时间复杂度 O(n)，其中 n 是 string 的长度s。

\n

实际上，对于 CPython 实现：在某些情况下，它们的复杂度可能都是 O(1)，因为解释器在检测到这是对s相关字符串的唯一引用时可以进行优化。

\n

演示（使用Python 3.10.1）：

\n

O(1)（游戏中的优化）：

\n

长度为 10\xe2\x81\xb9 的字符串，使用+=：

\n

$ python -m timeit --setup=\'s = "s" * 10**9\' \'s += "a"\'\n5000000 loops, best of 5: 96.6 nsec per loop\n

\n

长度为 10\xe2\x81\xb9 的字符串，使用+：

\n

$ python -m timeit --setup=\'s = "s" * 10**9\' \'s = s + "a"\'\n5000000 loops, best of 5: 95.5 nsec per loop\n

\n

长度为 1 的字符串，使用+=：

\n

$ python -m timeit --setup=\'s = "s"\' \'s += "a"\'\n5000000 loops, best of 5: 97 nsec per loop\n

\n

长度为 1 的字符串，使用+：

\n

$ python -m timeit --setup=\'s = "s"\' \'s = s + "a"\'\n5000000 loops, best of 5: 97.9 nsec per loop\n

\n

O(n)（优化不适用）：

\n

长度为 10\xe2\x81\xb9 的字符串，优化不适用，使用+=：

\n

$ python -m timeit --setup=\'s = "s" * 10**9; b = s\' \'s += "a"\'\n1 loop, best of 5: 440 msec per loop\n

\n

长度为 10\xe2\x81\xb9 的字符串，优化不适用，使用+：

\n

$ python -m timeit --setup=\'s = "s" * 10**9; b = s\' \'s = s + "a"\'\n1 loop, best of 5: 445 msec per loop\n

\n

长度为 1 的字符串，优化不适用，使用+=：

\n

$ python -m timeit --setup=\'s = "s"; b = s\' \'s += "a"\'\n5000000 loops, best of 5: 85.8 nsec per loop\n

\n

长度为 1 的字符串，优化不适用，使用+：

\n

$ python -m timeit --setup=\'s = "s"; b = s\' \'s = s + "a"\'\n5000000 loops, best of 5: 84.8 nsec per loop\n

\n

有关字符串连接时间复杂度的更多信息：\n /sf/answers/2599370931/ \n /sf/answers/2380573961/

\n