目录
我们经常讲的时间复杂度是对基本数据类型（int、float、char等）和基本语句（for、if、while、顺序结构等）的操作的时间计算，例如纯c语言编写的程序复杂度计算，但是大家都知道python程序有很多都是函数调用，例如列表的append()、insert（）函数等。例如：list.append() 我们不能说此语句就执行了一次，跟普通相加语法在执行时间相同，因此我们使用python内置的时间函数进行分析。
1.python内置类型性能分析
1.1timeit模块
timeit模块可以用来测试一小段Python代码的执行速度。
class timeit.Timer(stmt='pass', setup='pass', timer=<timer function>)
Timer是测量小段代码执行速度的类。
stmt参数是要测试的代码语句（statment），使用的是字符传入，需要加引号；
setup参数是运行代码时需要的设置；
timer参数是一个定时器函数，与平台有关。
timeit.Timer.timeit(number=1000000)
Timer类中测试语句执行速度的对象方法。number参数是测试代码时的测试次数，默认为1000000次。方法返回执行代码的平均耗时，一个float类型的秒数。
1.2 list操作测试
产生一个0~999的列表的不同操作测试：
def test1():
l = []
for i in range(1000):
l = l + [i]
def test2():
l = []
for i in range(1000):
l.append(i)
def test3():
l = [i for i in range(1000)]
def test4():
l = list(range(1000))
from timeit import Timer
t1 = Timer("test1()", "from __main__ import test1")#程序运行时test.py此文件是main
print("concat ",t1.timeit(number=1000), "seconds")
t2 = Timer("test2()", "from __main__ import test2")
print("append ",t2.timeit(number=1000), "seconds")
t3 = Timer("test3()", "from __main__ import test3")
print("comprehension ",t3.timeit(number=1000), "seconds")
t4 = Timer("test4()", "from __main__ import test4")
print("list range ",t4.timeit(number=1000), "seconds")
#运行结果：
# ('concat ', 1.7890608310699463, 'seconds')
# ('append ', 0.13796091079711914, 'seconds')
# ('comprehension ', 0.05671119689941406, 'seconds')
# ('list range ', 0.014147043228149414, 'seconds')分析：通过上述运行结果，我们可以经常使用列表生成表达式操作，减少使用加法操作，a[i] = a[i] + 1 和 a[i] += 1操作在python中也不一样,后者使用时间较短，可以测试
pop操作测试：
x = range(2000000)
pop_zero = Timer("x.pop(0)","from __main__ import x")
print("pop_zero ",pop_zero.timeit(number=1000), "seconds")
x = range(2000000)
pop_end = Timer("x.pop()","from __main__ import x")
print("pop_end ",pop_end.timeit(number=1000), "seconds")
# ('pop_zero ', 1.9101738929748535, 'seconds')
# ('pop_end ', 0.00023603439331054688, 'seconds')分析：从结果可以看出，pop最后一个元素的效率远远高于pop第一个元素，因为弹出首个元素值后面的元素都要向前移一位，遍历2000000次，运行时间较长，而弹出最后一位就不需要这样的过程，运行时间较短。可以自行尝试下list的append(value)和insert(0,value),即一个后面插入和一个前面插入？？？
1.3 list内置操作的时间复杂度
以下所有的操作都是要考虑最坏时间复杂度。
1.4 dict内置操作的时间复杂度
