Python数据结构与算法分析第2版 - 第2章习题

#2.1 设计一个实验，证明列表的索引操作为常数阶。

from timeit import Timer
import random
import numpy as np
from matplotlib import pyplot as plt
a = []
b = []
# 要证明这一点，需要看看两个操作在各个列表长度下的性能
popzero = Timer("x[200]","from __main__ import x")
# 测x[200]这个代码性能
# "from __main__ import x" 将x引入到timeit的计时命名空间
for i in range(1000000,100000001,1000000):
    b.append(i)  # 横轴
    x=list(range(i))  #生成不同长度的列表
    w=popzero.timeit(1000) #让其执行1000次得到的总时间数
    a.append(w)
 
plt.figure(figsize=(100,20))
plt.plot(b,a,'r.-',linewidth=2,ms=5)
my_x_ticks = np.arange(b[0],b[-1],1000000)
plt.xticks(my_x_ticks)
plt.show()

#2.2 设计一个实验，证明字典的取值操作和赋值操作为常数阶。

from timeit import Timer
import random
import numpy as np
from matplotlib import pyplot as plt
x1 = [] #用来存储x坐标
y