[数据结构与算法]Python Timer模块、list、dict、set内置操作复杂度

程序 = 数据结构 + 算法
抽象数据类型(ADT)的含义是指一个数学模型以及定义在此数学模型上的一组操作。引入抽象数据类型的目的是把数据类型的表示和运算的实现与这些数据类型和运算在程序中的引用隔开，使它们相互独立。

O(1) < O(logⁿ) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)

timeit.Timer

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

Timer测量小段代码执行速度的类。
stmt测试的代码语句（statment）；
setup运行代码时需要的设置；
timer一个定时器函数，与平台有关。

timeit.Timer.timeit(number=1000000)

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

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")
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')

list

dict

set