侧边栏壁纸
  • 累计撰写 122 篇文章
  • 累计创建 68 个标签
  • 累计收到 1 条评论

目 录CONTENT

文章目录

常见函数的时间复杂度

刘少锋
2019-05-25 / 0 评论 / 0 点赞 / 24 阅读 / 500 字

很多函数都有自己的很多方法,其中有些方法的功能类似,但是其复杂度有时却大不相同

本节我们将引入一个新模块 timeit ,其功能是来测试一小段 Python 代码的执行速度。

1、timeit

class timeit.Timer(stmt='pass', setup='pass',timer=<timer function>)
  • Timer 是测量小段代码执行速度的类

  • stmt 是要测试的代码语句 (statment), 字符串类型,

  • setup 是运行代码时需要的设置 , 字符串类型, 就是从 __main__ 引入需要的是的方法名

  • timer 参数是一个定时器函数, 与平台有关, 不用去管

  • timeit.Timer.timeit(numer=1000000)numer-> 测算次数, 返回平均耗时, 一个 float 类型的秒数

部分测试示例

p4tWrN

测试结果

Pjy5rN

2、list 的内置函数时间复杂度

方法复杂度简介
index[x]O(1)索引
index assignmentO(1)索引赋值
appendO(1)尾部追加
pop()O(1)尾部弹出
pop(i)O(n)指定位置弹出 n 列表长度, 最坏时间复杂度
insert(i, item)O(n)指定位置添加
del operatorO(n)删除, 代表一个一个元素去清空
iterationO(n)迭代
contains(in)O(n)看谁是否在列表中, 需要遍历
get slice[x:y]O(k)取切片, 从 x 取到 y, 一次定位到 x, 然后取到 y ,x 和 y 之间有多少就是 k
del sliceO(n)删除切片 删除位置之后, 后面的元素都需要往前移动
set sliceO(k)设置切片, li[0:3] = [1, 2, 3, 4]k 是补充的东西数量
reverseO(n)置返
concatenateO(k)代表使用的 +, 把两个列表加到一起, k 是第二个列表中的元素
sortO(nlogn)排序
multiplyO(nk)相乘 li=[1, 2] -> n li * 10 -> k

3、dict 的内置函数时间复杂度

方法复杂度简介
copyO(n)复制
get itemO(1)
set itemO(1)设置
delete itemO(1)删除键
contains(in)O(1)包含
iterationO(n)迭代
0

评论区