Python集合和时间复杂度
推荐
在线提问>>
在本文的这一部分中,我将记录CPython中的常见集合,然后概述它们的时间复杂性。
我将特别关注平均情况。
1.List
List是迄今为止Python中最重要的数据结构之一。我们可以将列表用作堆栈(添加的最后一项是第一项)或队列(添加的第一项是第一项)。列表是有序且可变的集合,因为我们可以随意更新项目。
让我们回顾一下常见列表操作及其Big-O表示法
插入:Big-O表示法是O(n)
获取项目:Big-O表示法为O(1)
删除项目:Big-O表示法是O(n)
迭代:Big-O表示法是O(n)
获得长度:Big-O表示法为O(1)
JoshuaSortino在Unsplash上拍摄的照片
2.Set
集合也是Python中使用最广泛的数据集合之一。集合本质上是无序集合。集合不允许重复,因此集合中的每个项目都是唯一的。集合支持许多数学运算,例如联合,差,集合的交集等。
让我们回顾一下通用Set操作
检查集合中的项目:Big-O表示法是O(1)
集合A与集合B的区别:大O表示法是O(A的长度)
集A和B的交集:大O表示法是O(A或B的长度的最小值)
集A和B的并集:相对于长度(A)+长度(B),它的Big-O表示法是O(N)
fabio在Unsplash上的照片
3.Dict字典
最后,我想提供字典数据收集的概述。字典是键值对集合。键在字典中是唯一的,以防止项目冲突。这是非常有用的数据收集。
字典由键索引,其中键可以是字符串,数字甚至是带有字符串,数字或元组的元组。
我们可以对字典执行许多操作,例如存储键的值,或基于键检索项目,或遍历项目等。
让我们回顾一下常见的词典时间复杂度:
在这里,我们认为该密钥用于获取,设置或删除项目。
获取项目:Big-O表示法为O(1)
设定项目:Big-O表示法是O(1)
删除项目:Big-O表示法是O(1)
遍历字典:Big-O表示法是O(n)
以上内容为大家介绍了Python集合和时间复杂度,希望对大家有所帮助,如果想要了解更多Python相关知识,请关注IT培训机构:千锋教育。http://www.mobiletrain.org/