设置python最坏情况的复杂度 [英] Sets python worst case complexity

问题描述

对python中集合的以下操作： x in s ; s是一个集合，其中

The following operation on sets in python : x in s ; where s is a set, has

平均情况：O（1），最坏情况：O（n）

Average case: O(1), and Worst Case: O(n)

有人可以解释这些复杂性吗？

Can someone explain these complexities ?

推荐答案

它被实现为哈希表。

哈希表（具有正确维护的负载因子）具有平均情况 O（1）的值，因为检查元素是否在列表中所需的预期操作数是恒定的，因此您只需要对元素进行哈希处理，然后访问表即可在所需的位置，检查bin，其中包含具有相同哈希值的所有元素-但此类元素的期望值是一个常量，取决于负载因子 ¹

A hash table (with properly maintained load factor) has an average case of O(1), since the expected number of operations needed to check if an element is in the list is constant, you just need to hash the element, access the table at the desired place, check the bin, which contains all elements with the same hash value - but the expected value of such elements is a constant that depends on the load factor¹

但是，在最坏的情况下，所有元素都具有相同的哈希值。结果是，当需要检查元素是否在集合中时，它需要遍历整个集合（在一个容器中），这基本上是线性扫描，并且是 O（n）

However, in the worst case, all the elements have the same hash values. This results that when needed to check if an element is in the set, it requires to traverse the entire collection (which is in one bin), which is basically a linear scan, and is O(n)

注意：上面说明了单独链接哈希表，但是对于打开寻址

Note: The above explains Separate Chaining hash tables, but the idea is similar for Open Addressing

（1）例如，如果加载系数为1/2，则表示不存在任何元素的概率所需的地址是1/2。 （恰好）1个元素在bin中的概率是1/4，恰好2个元素在那个bin中的概率是1/8，....

通过加总上述内容，您得到该bin中预期的元素数为 1/2 + 1/4 + 1/8 + ...< = 2

(1) If the load factor is 1/2 for example, it means the probability that no elements are in the desired address is 1/2. The probability that (exactly) 1 element is in the bin is 1/4, the probability that exactly 2 elements in that bin, is 1/8,....
By summing the above, you get that the expected number of elements in the bin is 1/2 + 1/4 + 1/8 + ... <= 2

这篇关于设置python最坏情况的复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！