python内置数据结构性能分析

栏目: IT技术 · 发布时间: 4年前

List

  1. 列表是一个类似数组的结构
  2. 对某个索引位置的获取和赋值的时间复杂度是O(1)
  3. 在列表末尾添加或删除一个元素的时间复杂度是O(1)
  4. 但是在列表除末尾之外的位置添加或删除一个元素的时间复杂度是O(n)。这是因为,在选定位置之后的元素需要被整体前移或后移
  5. 列表搜索的时间复杂度是O(n),因为列表搜索是靠遍历元素完成的
  6. 列表的extend时间复杂度是O(k),相当于在列表末尾插入k个元素
  7. 列表的sort函数内部实现机制为timesort,时间复杂度为O(nlogn),空间复杂度为O(n),是一种稳定的 排序 方法
    python内置数据结构性能分析

Dict

  1. 字典的底层实现是哈希表
  2. 字典是无序的,但可以使用collections.OrderedDict()实现有序字典。OrderedDict的实现原理是哈希表+双链表
  3. 字典的增删改查都是O(1)的时间复杂度
    python内置数据结构性能分析

Set

  1. 集合的底层实现是哈希表
  2. 集合的增删改查与字典一样,都是O(1)的时间复杂度
    python内置数据结构性能分析

collections.deque

  1. 双向队列的底层实现是双链表
  2. 一种对列表的改进:在头尾的增删都是O(1)的时间复杂度
  3. 但是在队列中的增删仍是O(n)的时间复杂度
  4. 查找也是O(n)的时间复杂度
    python内置数据结构性能分析

参考资料

https://runestone.academy/runestone/books/published/pythonds/AlgorithmAnalysis/Lists.html


以上所述就是小编给大家介绍的《python内置数据结构性能分析》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

算法引论

算法引论

[美]Udi Manber / 黄林鹏、谢瑾奎、陆首博、等 / 电子工业出版社 / 2005-9-1 / 35.00元

本书是国际算法大师乌迪·曼博(Udi Manber)博士撰写的一本享有盛誉的著作。全书共分12章:第1章到第4章为介绍性内容,涉及数学归纳法、算法分析、数据结构等内容;第5章提出了与归纳证明进行类比的算法设计思想;第6章到第9章分别给出了4个领域的算法,如序列和集合的算法、图算法、几何算法、代数和数值算法;第10章涉及归约,也是第11章的序幕,而后者涉及NP完全问题;第12章则介绍了并行算法;最后......一起来看看 《算法引论》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

URL 编码/解码
URL 编码/解码

URL 编码/解码

SHA 加密
SHA 加密

SHA 加密工具