很多函数都有自己的很多方法，其中有些方法的功能类似，但是其复杂度有时却大不相同；比如在列表函数中：
append() 和 insert()都是对元素的插入，但是头插和尾插的复杂度差别很大；
+ 和 extent()都是对列表的整体扩充，但是 + 执行的速度...
本节我们将引入一个新模块 timeit ，其功能是来测试一小段Python代码的执行速度。
1、timeit
class timeit.Timer(stmt='pass', setup='pass',timer=<timer function>)
a> Timer 是测量小段代码执行速度的类
b> stmt 是要测试的代码语句(statment), 字符串类型,
c> setup 是运行代码时需要的设置 ,字符串类型, 就是从 _main_ 引入需要的是的方法名
d> timer 参数是一个定时器函数, 与平台有关, 不用去管
e> timeit.Timer.timeit(numer=1000000)
f> numer->测算次数, 返回平均耗时, 一个float类型的秒数
部分测试示例
测试结果
2、list 的内置函数时间复杂度
| 方法 | 复杂度 | 简介 |
|---|---|---|
| index[x] | O(1) | 索引 |
| index assignment | O(1) | 索引赋值 |
| append | O(1) | 尾部追加 |
| pop() | O(1) | 尾部弹出 |
| pop(i) | O(n) | 指定位置弹出 n列表长度, 最坏时间复杂度 |
| insert(i, item) | O(n) | 指定位置添加 |
| del operator | O(n) | 删除, 代表一个一个元素去清空 |
| iteration | O(n) | 迭代 |
| contains(in) | O(n) | 看谁是否在列表中, 需要遍历 |
| get slice[x:y] | O(k) | 取切片, 从x取到y, 一次定位到x, 然后取到y ,x和y之间有多少就是k |
| del slice | O(n) | 删除切片 删除位置之后, 后面的元素都需要往前移动 |
| set slice | O(k) | 设置切片, li[0:3] = [1, 2, 3, 4]k是补充的东西数量 |
| reverse | O(n) | 置返 |
| concatenate | O(k) | 代表使用的+, 把两个列表加到一起, k是第二个列表中的元素 |
| sort | O(nlogn) | 排序 |
| multiply | O(nk) | 相乘 li=[1, 2] -> n li * 10 -> k |
3、dict 的内置函数时间复杂度
| 方法 | 复杂度 | 简介 |
|---|---|---|
| copy | O(n) | 复制 |
| get item | O(1) | 取 |
| set item | O(1) | 设置 |
| delete item | O(1) | 删除键 |
| contains(in) | O(1) | 包含 |
| iteration | O(n) | 迭代 |
