四种不同的列表构造方法的时间复杂度比较

先附上代码

import time
import  matplotlib.pyplot as plt

def test1(n):
    lst=[]
    for i in range(n*10000):
        lst+=[i]
    return lst

def test2(n):
    lst=[]
    for i in range(n*10000):
        lst.append(i)
    return lst

def test3(n):
    return [i for i in range(n*10000)]

def test4(n):
    return list(range(n*10000))


x=range(1000)
y=[[],[],[],[]]
for n in x:
    print(n)
    start=time.time()
    test1(n)
    y[0].append(time.time()-start)

    start=time.time()
    test2(n)
    y[1].append(time.time()-start)

    start = time.time()
    test3(n)
    y[2].append(time.time()-start)

    start = time.time()
    test4(n)
    y[3].append(time.time()-start)

for i in range(4):
    plt.plot(x,y[i],label='test%d'%(i+1))
plt.legend()
plt.show()

结果如下图所示

可以看出，四种不同构造列表方式的时间复杂度可认为都为O(n)，只是系数不同，因此还是有所差异的。第1种方式和第2种方式的时间复杂度相当，可见用单元素列表拼接的方式扩充列表与直接将元素插在列表最后的方式具有同样的效率。生成式方法效率优于以上两种，但低于直接构造列表的方式。
同时，可以明显看出1,2,3种方法的时间复杂度曲线都存在间隔明显的突起，这是python列表的构造机制造成的。因为在列表插入元素时采用的是动态扩充容量的机制，当列表容量满时，pyhon会将列表复制到更大的一块内存，以扩充其容量，这个操作的耗时是正比于元素个数的。