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)$，比如二分查找。