Python数据结构的时间复杂性

摘要

本文介绍了CPython中数据结构的关键操作的Big-O表示法。 big-o标记本质上是一种衡量操作时间复杂度的方法。本文还说明了列表，集合和字典的许多常用操作。

为算法设计和选择正确的数据结构至关重要。

希望能帮助到你。

为什么我们需要知道时间复杂性?

对于数据科学家程序员而言，为工作选择正确的数据结构至关重要。特别是，如果算法需要大量计算，例如训练机器学习模型的算法或处理大量数据的算法，那么确保选择合适的数据结构时要特别小心。

选择正确的数据类型通常会被忽略，并且最终会严重影响应用程序的性能。

文章目的

本文介绍了CPython中数据结构的关键操作的Big-O表示法。 big-O表示法是一种衡量操作时间复杂度的方法。

1.让我们了解大O符号的含义是什么?

在算法中执行许多操作。这些操作可能包括遍历集合，复制项目或整个集合，将项目追加到集合中，在集合的开始或结尾处插入项目，删除项目或更新集合中的项目。

Big-O衡量算法运算的时间复杂度。它测量算法计算所需运算所需的时间。尽管我们也可以测量空间复杂度(算法占用多少空间)，但本文将重点介绍时间复杂度。

用最简单的术语来说，Big O表示法是一种基于输入大小(称为n)来衡量操作性能的方法。

2. Big O表示法有何不同?

我们需要熟悉许多常见的Big O符号。

让我们考虑n为输入集合的大小。就时间复杂度而言：

O(1)：无论您的集合有多大，执行操作所花费的时间都是恒定的。这是恒定的时间复杂度符号。这些操作尽可能快。例如，检查集合内部是否有任何项目的操作是O(1)操作。
O(log n)：当集合的大小增加时，执行操作所花费的时间对数增加。这是对数时间复杂度表示法。潜在优化的搜索算法为O(log n)。
O(n)：执行操作所需的时间与集合中的项目数成线性正比。这是线性时间复杂度符号。就性能而言，这介于两者之间或中等。作为一个实例，如果我们想对一个集合中的所有项目求和，那么我们将不得不遍历该集合。因此，集合的迭代是O(n)操作。
(n log n)：执行某项操作的性能是集合中项目数量的拟线性函数。这称为准线性时间复杂度表示法。优化排序算法的时间复杂度通常为n(log n)。
O(n平方)：执行操作所需的时间与集合中项目的平方成正比。这称为二次时间复杂度表示法。
(n!)：当在操作中计算集合的每个单个排列时，因此执行操作所需的时间取决于集合中项目的大小。这称为阶乘时间复杂度表示法。非常慢。

该图像概述了Big-O符号。