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

Question

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

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

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

Answer 1

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

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

实际上，对于 CPython 实现：它们在某些情况下都可以是 O(1)，因为解释器会进行优化。

演示（使用Python 3.10.1）：

O(1)（正在优化）：

长度为 10⁹ 的字符串，使用 +=:

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

长度为 10⁹ 的字符串，使用 +:

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

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

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

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

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

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

长度为 10⁹ 的字符串，优化不适用，使用 +=:

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

长度为 10⁹ 的字符串，优化不适用，使用 +:

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

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

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

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

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

有关字符串连接时间复杂度的更多信息：

Answer 2

Python 中的字符串是不可变的，因此每当您“追加”到 s 时，Python 都会制作 s 的副本并追加新字符，有效地使两者的时间复杂度为 O(n) .