Python核心数据结构时间复杂度

为什么？

对于编程来说，选择正确的数据结构是至关重要的。

特别是，如果算法是计算密集型的，例如训练机器学习模型的算法或处理大数据的算法，那么认真仔细的选择合适的数据结构是必要前提工作。如果使用了不合适的数据结构，最终会严重影响应用程序的性能。

孙子兵法: “先胜而后战，先战而后败”！ 思考如何组织数据，已经立于编程不败之地了！

所以接下来，给大家分享下如何评估时间复杂度以及Python核心数据结构的复杂度。

本文解释了 Python 中数据结构关键操作的 Big-O 表示法。 Big-O 表示法是一种测量操作时间复杂度的方法。

什么是Big-O表示法？

在一个算法中会执行许多操作。这些操作包括迭代集合，复制元素或整个集合，将元素附加到集合，在集合的开头或结尾插入元素，删除元素或更新集合中的元素。

Big-O 用来衡量操作的时间复杂度。它测量算法运行需要花费的时间。同时也可以测量空间复杂度（算法占用空间），但本文将重点关注时间复杂度。

简单地说，Big-O是一种基于输入大小（$n$）来衡量操作性能的表示方法。

有哪些不同的Big-O符号？

假设程序输入的大小为 $n$ ,让我们来看下常见的Big-O符号。

• $O(1)$: 无论输入的 $n$ 有多大，执行操作所需的时间恒定。这是常数复杂度，最快的算法。例如，检查集合中是否存在元素，时间复杂度是 $O(1)$。

• $O(logn)$: 随着输入的增加，执行操作所需的时间呈对数增加。这是对数时间复杂度。一般优化后搜索算法是$O(logn)$，比如二分查找。

• $O(n)$: 随着输入的增加，执行操作所需的时间呈线性增加。这是线性时间复杂度。就性能而言，属于中等。 例如，如果想对一个集合中的所有元素求和，那么必须遍历该集合中的全部元素。 因此时间复杂度是$O(n)$。

• $O(nlogn)$: 快速排序算法的时间复杂度通常为$O(nlogn)$。

• $O(n^2)$: 平方时间度复杂度，如两层嵌套的循环。

• $O(n!)$: 阶乘时间复杂度，它非常缓慢。

下图提供了时间复杂度的概述。 $O(1)$是最快的，$O(n^2)$是慢的，$O(n!)$是最慢的！

Big-O 表示法是独立于机器的，忽略系数的，被数学家、技术专家、数据科学家广泛使用。

最好的、平均的、最坏的情况

当我们计算一个操作的时间复杂度时，可以根据最好的、平均的或最坏的情况产生复杂度。

1. 最佳情况： 顾名思义，这些是数据结构和集合中的元素以及参数处于最佳状态时的情况。例如，假设要在集合中查找元素，而该元素恰好是集合的第一个元素，那么它是该操作的最佳情况。
2. 平均情况： 是根据输入值的分布来定义复杂性。
3. 最坏情况： 可能是这样一种操作，它需要在大型集合（例如列表）中查找元素，而这个元素是最后一个元素，需要遍历集合的所有元素才能找到。

Python 数据结构 和 时间复杂度

接下来就是重点！！！分享 Python 中的常见数据结构，并介绍它们的时间复杂度。注意，我们专注于平均情况。

列表

列表是迄今为止 Python 中最重要的数据结构之一。可以将列表用作堆栈（添加的最后一项是第一个输出）或队列（添加的第一个项目是第一个输出）。列表是有序且可变的集合，而且可以随意更新列表。

列表常见操作的时间复杂度：

• 插入：$O(1)$
• 获取：$O(n)$
• 删除：$O(n)$
• 迭代：$O(n)$
• 获取长度：$O(1)$

集合

集合也是 Python 中使用最广泛的数据集合之一。python集合本质上是一个无序的集合。集合不允许重复，因此集合中的每个项目都是唯一的。集合支持并集、差集、集合的交集等多种数学运算。

集合常见操作的时间复杂度：

• 集合是否有元素：$O(1)$

• 求集合B与A的差：$O(n_A)$

• 集合A和B的交集：$O(min(n_A,n_B))$

• 集合A和B的并集：$O(n_A+n_B)$

字典

最后，分享下字典这一数据结构。字典是一个键值对集合。键在字典中是唯一的，以防止项目冲突。这是一个非常有用的特性。

字典由键索引，其中键可以是字符串、数字甚至是带有字符串、数字或元组的元组。

我们可以对字典执行许多操作，例如存储键的值，或基于键检索项目，或遍历元素等。

字典常见操作的时间复杂度：

• 获取元素：$O(1)$
• 更新元素：$O(1)$
• 删除元素：$O(1)$
• 遍历字典：$O(n)$

小节

本文介绍了 Python 中常见数据结构相关操作复杂的的Big-O表示法。Big-O表示法本质上是一种衡量操作时间复杂度的方法。

希望通过上面的分享，将来你在编程或工作时，面对问题可以正确的评估选择合适的数据结构，从而设计一个完美、健壮的程序！