为什么?
对于编程来说,选择正确的数据结构是至关重要的。
特别是,如果算法是计算密集型的,例如训练机器学习模型的算法或处理大数据的算法,那么认真仔细的选择合适的数据结构是必要前提工作。如果使用了不合适的数据结构,最终会严重影响应用程序的性能。
孙子兵法: "先胜而后战,先战而后败"! 思考如何组织数据,已经立于编程不败之地了!
所以接下来,给大家分享下如何评估时间复杂度以及Python核心数据结构的复杂度。
本文解释了 Python 中数据结构关键操作的 Big-O 表示法。 Big-O 表示法是一种测量操作时间复杂度的方法。
什么是Big-O表示法?
在一个算法中会执行许多操作。这些操作包括迭代集合,复制元素或整个集合,将元素附加到集合,在集合的开头或结尾插入元素,删除元素或更新集合中的元素。
Big-O 用来衡量操作的时间复杂度。它测量算法运行需要花费的时间。同时也可以测量空间复杂度(算法占用空间),但本文将重点关注时间复杂度。
简单地说,Big-O是一种基于输入大小(
)来衡量操作性能的表示方法。
有哪些不同的Big-O符号?
假设程序输入的大小为
,让我们来看下常见的Big-O符号。
-
: 无论输入的
有多大,执行操作所需的时间恒定。这是常数复杂度,最快的算法。例如,检查集合中是否存在元素,时间复杂度是
。
-
: 随着输入的增加,执行操作所需的时间呈对数增加。这是对数时间复杂度。一般优化后搜索算法是
,比如二分查找。
-
: 随着输入的增加,执行操作所需的时间呈线性增加。这是线性时间复杂度。就性能而言,属于中等。 例如,如果想对一个集合中的所有元素求和,那么必须遍历该集合中的全部元素。 因此时间复杂度是
。
-
: 快速排序算法的时间复杂度通常为
。
-
: 平方时间度复杂度,如两层嵌套的循环。
-
: 阶乘时间复杂度,它非常缓慢。
下图提供了时间复杂度的概述。
是最快的,
是慢的,
是最慢的!
Big-O 表示法是独立于机器的,忽略系数的,被数学家、技术专家、数据科学家广泛使用。
最好的、平均的、最坏的情况
当我们计算一个操作的时间复杂度时,可以根据最好的、平均的或最坏的情况产生复杂度。
- 最佳情况: 顾名思义,这些是数据结构和集合中的元素以及参数处于最佳状态时的情况。例如,假设要在集合中查找元素,而该元素恰好是集合的第一个元素,那么它是该操作的最佳情况。
- 平均情况: 是根据输入值的分布来定义复杂性。
- 最坏情况: 可能是这样一种操作,它需要在大型集合(例如列表)中查找元素,而这个元素是最后一个元素,需要遍历集合的所有元素才能找到。
Python 数据结构 和 时间复杂度
接下来就是重点!!!分享 Python 中的常见数据结构,并介绍它们的时间复杂度。注意,我们专注于平均情况。
列表
列表是迄今为止 Python 中最重要的数据结构之一。可以将列表用作堆栈(添加的最后一项是第一个输出)或队列(添加的第一个项目是第一个输出)。列表是有序且可变的集合,而且可以随意更新列表。
列表常见操作的时间复杂度:
- 插入:
- 获取:
- 删除:
- 迭代:
- 获取长度:
集合
集合也是 Python 中使用最广泛的数据集合之一。python集合本质上是一个无序的集合。集合不允许重复,因此集合中的每个项目都是唯一的。集合支持并集、差集、集合的交集等多种数学运算。
集合常见操作的时间复杂度:
-
集合是否有元素:
-
求集合B与A的差:
-
集合A和B的交集:
-
集合A和B的并集:
字典
最后,分享下字典这一数据结构。字典是一个键值对集合。键在字典中是唯一的,以防止项目冲突。这是一个非常有用的特性。
字典由键索引,其中键可以是字符串、数字甚至是带有字符串、数字或元组的元组。
我们可以对字典执行许多操作,例如存储键的值,或基于键检索项目,或遍历元素等。
字典常见操作的时间复杂度:
- 获取元素:
- 更新元素:
- 删除元素:
- 遍历字典:
小节
本文介绍了 Python 中常见数据结构相关操作复杂的的Big-O表示法。Big-O表示法本质上是一种衡量操作时间复杂度的方法。
希望通过上面的分享,将来你在编程或工作时,面对问题可以正确的评估选择合适的数据结构,从而设计一个完美、健壮的程序!
上面只是Python数据结构复杂度的冰山一角,感兴趣的同学可以点击python数据结构与算法,总共88个小节,592张精美插图,系统介绍数据结构及其Python编码实现。
如果觉得还可以,点赞收藏,好人一生平安 。
pythontip 出品,Happy Coding!
原文链接,代码中在线运行
公众号: 夸克编程
近期评论