算法Time复杂度（Python）

1、timeit模块：

timeit模块可以用来测试一小段python代码的执行速度

class timeit.Timer(stmt = 'pass', setup = 'pass', timer = <timer function>)

• Timer 是测量小段代码执行速度的类
• stmt 参数是要测试的代码语句
• setup 参数是运行代码时需要的设置
• timer 参数是一个定时器函数

timeit.Timer.timeit(number=1000000)

Timer类中测试语句执行速度的对象方法。number参数是测试代码时的测试次数，默认为 1000000 次。方法返回执行代码的平均耗时，一个 float 类型的秒数。

# -*- coding: utf-8 -*-

from timeit import Timer


def test1():
    li = []
    for i in range(10000):
        li.append(i)

def test2():
    li = []
    for i in range(10000):
        li += [i]

def test3():
    li = []
    for i in range(10000):
        li += [i]

def test4():
    li = [i for i in range(10000)]

def test5():
    li = list(range(10000))

def test6():
    li = []
    for i in range(10000):
        li.extend([i])

def test7():
    li = []
    for i in range(10000):
        li.append(i)

def test8():
    li = []
    for i in range(10000):
        li.insert(0, 1)

t1 = Timer('test1()', 'from __main__ import test1')
print('append:\t' ,t1.timeit(number=1000), "seconds")
t2 = Timer('test2()', 'from __main__ import test2')
print('+方式:\t：' ,t2.timeit(number=1000), "seconds")
t3 = Timer('test3()', 'from __main__ import test3')
print('+=方式:\t' ,t3.timeit(number=1000), "seconds")
t4 = Timer('test4()', 'from __main__ import test4')
print('rang()方式:\t' ,t4.timeit(number=1000), "seconds")
t5 = Timer('test5()', 'from __main__ import test5')
print('list:\t' ,t4.timeit(number=1000), "seconds")
t6 = Timer('test6()', 'from __main__ import test6')
print('extend:\t' ,t6.timeit(number=1000), "seconds")
t7 = Timer("test7()", "from __main__ import test7")
print("append:\t", t7.timeit(number=1000), "second")
t8 = Timer("test8()", "from __main__ import test8")
print("insert:\t:", t8.timeit(number=1000), "second")

append:	 0.540883 seconds
+方式:	： 0.7580815999999999 seconds
+=方式:	 0.7634606999999998 seconds
rang()方式:	 0.28493109999999966 seconds
list:	 0.2858050999999997 seconds
extend:	 0.8201059000000002 seconds
append:	 0.5261513999999998 second
insert:	: 20.339980399999998 second

总结

不同的构造列表方式的速度排序：
‘list[range()]’ < ‘列表推导式’ < ‘+=’ < ‘append’ < ‘extend’ < ‘insert’ < ‘+’
推荐使用 ‘list[range()]’、‘列表推导式’、’+=’、‘append’、‘extend’，尽量避免使用 ‘insert’ 和 ‘+’ 的方式来构建列表
‘list[range()]’ 方式构建列表速度最快
‘+=’、‘append’、‘extend’ 构建列表速度相近
‘+’ 方式速度最慢