Python数据结构的时间复杂性

发布时间:2022-03-23 10:00:40 人气:35 作者:多测师

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

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

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

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

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

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

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

  O(1):无论您的集合有多大,执行操作所花费的时间都是恒定的。 这是恒定的时间复杂度符号。 这些操作尽可能快。 例如,检查集合内部是否有任何项目的操作是O(1)操作。

  O(log n):当集合的大小增加时,执行操作所花费的时间对数增加。 这是对数时间复杂度表示法。 潜在优化的搜索算法为O(log n)。

Python数据结构的时间复杂性

  O(n):执行操作所需的时间与集合中的项目数成线性正比。 这是线性时间复杂度符号。 就性能而言,这介于两者之间或中等。 作为一个实例,如果我们想对一个集合中的所有项目求和,那么我们将不得不遍历该集合。 因此,集合的迭代是O(n)操作。

  (n log n):执行某项操作的性能是集合中项目数量的拟线性函数。 这称为准线性时间复杂度表示法。 优化排序算法的时间复杂度通常为n(log n)。

  O(n平方):执行操作所需的时间与集合中项目的平方成正比。 这称为二次时间复杂度表示法。

  (n!):当在操作中计算集合的每个单个排列时,因此执行操作所需的时间取决于集合中项目的大小。 这称为阶乘时间复杂度表示法。 非常慢。

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

  O(1)很快。 O(n平方)很慢。 O(n!)非常慢。

  大O符号是相对的。 大O表示法与机器无关,忽略常量,并且被包括数学家,技术人员,数据科学家等在内的广泛读者所理解。

  最佳,平均,最差情况

  当我们计算操作的时间复杂度时,我们可以根据最佳,平均或最坏情况产生复杂度。

  最佳情况方案:顾名思义,这是当数据结构和集合中的项目以及参数处于最佳状态时的方案。 例如,假设我们要在集合中找到一个项目。 如果该项目恰好是集合的第一项,那么这是该操作的最佳情况。

  平均情况是根据输入值的分布定义复杂度。

  最坏的情况是可能需要一种操作,该操作需要在大型集合(例如列表)中找到位于最后一个项目的项目,并且算法会从第一个项目开始对集合进行迭代。

  以上内容为大家介绍了Python数据结构的时间复杂性,希望对大家有所帮助,如果想要了解更多Python相关知识,请关注多测师。https://www.e70w.com/xwzx/

返回列表
在线客服
联系方式

热线电话

17727591462

上班时间

周一到周五

二维码
线