此列表代码的附加和连接的复杂性有何不同？

考虑以下形成千个数字列表的方法。

def test1():
    l = []
    for i in range(1000):
        l = l + [i]
    return l


def test2():
    l = []
    for i in range(1000):
        l.append(i)    

print timeit.repeat(stmt=test1, number=100,repeat=2)
print timeit.repeat(stmt=test2, number=100,repeat=2)

Output:

[0.30474191033602543, 0.3783786557587963]
[0.015134341605235302, 0.023081246200096328]

为什么追加方法比串联方法好 20 倍左右。 AFAIK 追加的复杂度为 O(1)，而串联的复杂度为 O(k)。而这里的K是1。

有什么明显的事情我忽略了吗？

您正在创建一个new每次通过连接列出对象。这需要将旧列表中的所有元素复制到新列表中，再加上一个额外的元素。所以是的，使用l = l + [i]是 O(N) 算法，而不是 O(1)。

至少不要使用+级联;使用+= 增强的连接，这与list.extend()重新分配给相同的引用：

def test3():
    l = []
    for i in range(1000):
        l += [i]  # or use l.extend([i])
    return l

这会产生：

>>> print timeit.repeat(stmt=test1, number=100, repeat=2)
[0.1333179473876953, 0.12804388999938965]
>>> print timeit.repeat(stmt=test2, number=100, repeat=2)
[0.01052403450012207, 0.007989168167114258]
>>> print timeit.repeat(stmt=test3, number=100, repeat=2)
[0.013209104537963867, 0.011193037033081055]