分析pop()和pop(i)的性能差异-python

￡神魔★判官ぃ 2023-07-10 08:41 13阅读 0赞

> 《Python数据结构与算法分析》（第二版）

**pop()时间复杂度O(1)  
pop(i)时间复杂度O(n)**

**1. 针对一个已知长度的列表，分别从列表头和列表尾弹出一个元素**

import timeit
    
    x = list(range(2000000))
    y = list(range(2000000))
    
    # 在测试中使用列表对象x，可以只对pop语句计时，从而准确得到这个操作的耗时
    # 因为重复计时了1000次，所以列表每次循环都少一个元素，但列表的初始长度是200万，因此对整体长度来说，只减少了0.05%
    popzero = timeit.Timer("x.pop(0)", "from __main__ import x")
    print("pop(0) ", popzero.timeit(number=1000))
    
    popend = timeit.Timer("y.pop()", "from __main__ import y")
    print("pop() ", popend.timeit(number=1000))

运行结果：  
![在这里插入图片描述][20200301165507693.PNG]  
测试结果虽然说明pop(0)确实比pop()慢，但并没有证明pop(0)的时间复杂度是O(n)，也没有证明pop()的时间复杂的是O(1)，故需要进一步测试这两个操作在不同列表长度下的性能。

**2. 比较pop(0)和pop()在不同列表长度下的性能**

import timeit
    
    popzero = timeit.Timer("x.pop(0)", "from __main__ import x")
    popend = timeit.Timer("x.pop()", "from __main__ import x")
    print("pop(0) pop()")
    for i in range(1000000, 100000001, 1000000):#循环100次
        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))

运行结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc5MDM2MA_size_16_color_FFFFFF_t_70]  
从测试结果可以看出，列表越长，pop(0)的耗时也随之变长，而pop()的耗时很稳定。

[20200301165507693.PNG]: https://img-blog.csdnimg.cn/20200301165507693.PNG
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc5MDM2MA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200301165150873.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc5MDM2MA==,size_16,color_FFFFFF,t_70