x += y 和 x = x + y 之间的执行时间差

Question

我试图将我的解决方案提交给 leetcode 问题，其中x和y是列表和使用

x = x + y

给我一个时间超过限制 而使用

x += y

通过了测试用例并给了我AC。

两者之间的执行时间差异以及两者执行方式的差异是多少？

Answer 1

对于列表对象，

temp = temp + [] 

创建一个新列表，并在结果列表的大小上花费线性时间（线性缩放）。重要的是，它重新创建了整个新列表。如果在循环中完成，例如

x = []

for i in range(N):
    x = x + [i]

整个算法是二次时间，O(N^2)

另一方面，temp += []就地工作。它不会创建新列表。它是 O(K)，其中 K 是右侧列表的大小，即添加的元素数。这是因为 python 列表对象被实现为过度分配的数组列表，因此您不必在每次列表大小增加时重新分配。简而言之，这意味着将项目附加到列表末尾是摊销常数 time。重要的是，这使得：

x = []

for i in range(N):
    x += [i]

线性时间，即 O(N)。

要凭经验查看此行为，您可以使用以下脚本：

import pandas as pd
import matplotlib.pyplot as plt
import time

def concatenate(N):
    result = []
    for i in range(N):
        result = result + [i]

def inplace(N):
    result = []
    for i in range(N):
        result += [i]


def time_func(N, f):
    start = time.perf_counter()
    f(N)
    stop = time.perf_counter()
    return stop - start

NS = range(0, 100_001, 10_000)
inplc = [time_func(n, inplace) for n in NS]
concat = [time_func(n, concatenate) for n in NS]

df = pd.DataFrame({"in-place":inplc, "concat": concat}, index=NS)

df.plot()
plt.savefig('in-place-vs-new-list-loop.png')

请注意，在 a 处N == 100_000，连接版本需要 10 秒以上，而就地扩展版本需要 0.01 秒……所以它慢了几个数量级，并且随着 N 的增加，差异将继续急剧增长（即二次方）。

为了理解这种行为，这里是时间复杂度的非正式处理：

对于 concat，在每次迭代中都x = x + [i]需要进行i大量工作，其中i是结果数组的长度。所以整个循环将是0 + 1 + 2 + 3 + ... + N. 现在，使用这个著名系列的第 N 个部分和的方便公式，循环将需要 N*(N+1)/2 总工作量。

N*(N + 1) / 2 == N^2/2 + N/2 就是 O(N^2)

另一方面，就地扩展版本，在每次迭代中，

temp += [i]

只需要1（恒定）工作量。所以对于整个循环，它只是

1 + 1 + ... + 1（N 次）

所以 N 总工作量，所以它是 O(N)