数据结构与算法python版本之列表和字典复杂度

前面我们了解了大O表示法以及对不同算法的预估
接下来我们讨论python两种内置数据类型（列表和字典）上各种操作的大O数量级

列表数据类型

list类型各种操作的实现方法很多，如何选择具体哪种实现方法。总的方案就是，让最常用的操作性能最好，牺牲不太常用的操作。一般我们使用80/20原则——80%的功能其使用率只有20%；
列表最常用的操作是：按索引取值和赋值，比如说是v =a[i]，a[i]=v，由于列表的随机访问特性，这两个操作执行时间与列表大小无关，均为O(1)
另一个最常用的是列表增长，我们可以选择append()和_add_()“+”；
list.append(v)，执行时间是O(1)
lst=lst+[v]，执行时间是O(n+k)，其中k是被加的列表长度；
以上，我们选择哪个方法来操作列表，决定了程序的性能将会是什么样子的

所以我们接下来举个例子，以生成前n个整数列表的方法来进行测试

#循环连接列表方式生成
def test1():
    l = []
    for i in range(1000):
        l = l + [i]

#利用append方法添加元素生成
def test2():
    l = []
    for i in range(1000):
        l.append(i)

#用列表推导式来实现
def test3():
    l = [i for i in range(1000)]

#利用range函数调用转成列表
def test4():
    l = list(range(1000))

接下来使用timeit模块对函数计时
创建一个Timer对象，指定需要反复运行的语句和只需要运行一次的“安装语句"
然后调用这个对象的timeit方法，其中可以指定反复运行多少次

from timeit import Timer
t1 = Timer("test1()","from __main__ import test1")
print("concat %f seconds\n" % t1.timeit(number = 1000))
t2 = Timer("test2()","from __main__ import test2")
print("append %f seconds\n" % t2.timeit(number = 1000))
t3= Timer("test3()","from __main__ import test3")
print("comprehension %f seconds\n" % t3.timeit(number = 1000))
t4= Timer("test4()","from __main__ import test4")
print("list range %f second\n" % t4.timeit(number = 1000))

我们运行之后的结果是

D:\code\hwt\venv\Scripts\python.exe D:\code\hwt\test_b.py 
concat 0.906821 seconds

append 0.037925 seconds

comprehension 0.019203 seconds

list range 0.007087 second


Process finished with exit code 0

我们可以看到：
这四种方法运行时间差别很大：列表连接（concat）最慢，List range最快，速度相差近200倍。
append也要比concat快得多；另外，我们注意到列表推导式速度是append两倍的样子

这个是列表增加的操作，那么列表的删除操作的性能怎么样呢，我们来进行一下list.pop的计时试验
我们注意到pop这个操作，pop()它是从列表末尾移除元素，O(1)；pop(i)从列表中部移除元素，O(n)，这个的原因在于Python所选择的实现方法：从中部移除元素的话，要把移除元素后面的元素全部向前挪位复制一遍，这个看起来有点笨拙，但这种实现方法能够保证列表按索引取值和赋值的操作很快，达到O(1)，这也算是一种对常用和不常用操作的折衷方案

为了验证表中的大O数量级，我们把两种情况下的pop操作来实际计时对比，相对同一个大小的list，分别调用pop()和pop(0)
对于大小不同的list做计时时，期望的结果是：pop()的时间不随list大小变化，pop(0)的时间随着list变大而边长

x = list(range(2000000))

import timeit
popzero = timeit.Timer("x.pop(0)", "from __main__ import x")
print(popzero.timeit(number=1000))
popend = timeit.Timer("x.pop()", "from __main__ import x")
print(popend.timeit(number=1000))

运行结果是

D:\code\hwt\venv\Scripts\python.exe D:\code\hwt\test_b.py 
1.2591895
3.379999999997274e-05

Process finished with exit code 0

首先我们看对比
对于长度两百万的列表，执行1000次
pop()时间是1.26
pop(0)时间是0.0000338
相差1000多倍

接下来我们通过改变列表的大小来测试两个操作的增长趋势
我们使用如下代码

x = list(range(2000000))

import timeit
popzero = timeit.Timer("x.pop(0)", "from __main__ import x")
print(popzero.timeit(number=1000))
popend = timeit.Timer("x.pop()", "from __main__ import x")
print(popend.timeit(number=1000))

print("pop(0)  pop()")
for i in range(1000000, 100000001, 1000000):
    x = list(range(i))
    pt = popend.timeit(number=1000)
    x = list(range(i))
    pz = popzero.timeit(number=1000)
    print("%15.5f, %15.5f" %(pz,pt))

运行之后我们发现

D:\code\hwt\venv\Scripts\python.exe D:\code\hwt\test_b.py 
1.3254912
3.1899999999973616e-05
pop(0)  pop()
        0.63952,         0.00010
        1.27070,         0.00005
        1.89366,         0.00005
        2.51875,         0.00007
        3.16086,         0.00008
        3.79605,         0.00006
        4.42389,         0.00010
        5.03627,         0.00005
        5.73751,         0.00007
        6.31563,         0.00005
        6.98311,         0.00005
        7.59439,         0.00004
        8.27622,         0.00005
        8.86239,         0.00006
        9.49110,         0.00005
       10.17818,         0.00005
       10.84629,         0.00008
       11.36126,         0.00005
       12.01135,         0.00005
       12.63843,         0.00005
       13.28525,         0.00006
       14.00205,         0.00005
       14.34231,         0.00005
       15.26307,         0.00006
       15.82224,         0.00005
       16.43155,         0.00006
       17.22533,         0.00005
       17.30603,         0.00005
       18.44659,         0.00005
       18.92079,         0.00005
       19.54118,         0.00005
       20.26459,         0.00005
       20.73825,         0.00007
       21.25046,         0.00005
       22.14043,         0.00006
       22.65790,         0.00005
       23.24152,         0.00011
       23.80041,         0.00005
       24.32684,         0.00005
       25.06700,         0.00012
       25.61303,         0.00005
       26.03183,         0.00005
       27.01421,         0.00005
       27.64547,         0.00006
       28.23284,         0.00005
       28.85573,         0.00007
       29.40643,         0.00009
       30.18097,         0.00005
       30.76568,         0.00008
       31.37746,         0.00005
       32.13112,         0.00005
       32.76765,         0.00005
       33.18907,         0.00006
       34.00520,         0.00006
       34.86553,         0.00005
       35.42342,         0.00007
       35.97052,         0.00005
       36.49784,         0.00007
       37.18589,         0.00009
       37.90012,         0.00006
       38.47604,         0.00009
       39.01364,         0.00007
       39.75864,         0.00007
       40.56032,         0.00007
       41.15358,         0.00007
       41.54546,         0.00006
       42.07594,         0.00006
       42.79207,         0.00005
       43.54447,         0.00005
       44.22097,         0.00005
       44.84709,         0.00005
       45.58542,         0.00008
       46.34520,         0.00006
       46.84686,         0.00005
       47.26888,         0.00006
       47.87076,         0.00009
       48.38534,         0.00005
       49.30737,         0.00005
       49.87582,         0.00007
       50.44976,         0.00005
       51.15869,         0.00007
       51.60122,         0.00005
       52.67146,         0.00006
       52.78433,         0.00005
       53.45289,         0.00006
       54.47275,         0.00008
       55.11775,         0.00008
       55.67943,         0.00006
       56.17295,         0.00006
       56.54980,         0.00006
       57.16567,         0.00006
       58.05508,         0.00008
       58.64530,         0.00005
       59.73103,         0.00006
       59.55753,         0.00006
       60.52892,         0.00006
       61.33431,         0.00006
       61.40680,         0.00005
       62.17889,         0.00005
       62.72137,         0.00006

Process finished with exit code 0

我们可以看到右边这一列基本没什么变化，左边这一列呢基本上都是一个线性的方式增长上去的，我们简单画个图

我们可以看到pop()是平坦的常数，而pop(0)存在线性增长的趋势，当时，也会有额外几个小点跳出去，这些都是正常的，因为多用户的操作的情况下，会存在许多极其特殊的情况，这都是可以解释的。

字典与列表不同，根据关键码（key）找到数据项，而列表是根据位置（index）最常用的取值get和赋值set，其性能为O(1)，另一个重要的操作contains(in)是判断字典中是否存在某个关键码（key）是否存在，这个性能也是O(1)
list和dict的in操作对比，我们同样也可以设计一个性能试验来验证list中检索一个值以及dict中检索一个值的计时对比
我们也会得出结论：
字典的执行时间与规模无关，是常数
列表的执行时间则随着列表的规模加大而线性上升
python官方的算法复杂度网站https://wiki.python.org/moin/TimeComplexity