Python中集差函数的运行时间是多少? [英] What is the run time of the set difference function in Python?

问题描述

问题解释了，但是Python中的集差运算的时间复杂度是多少?

The question explains it, but what is the time complexity of the set difference operation in Python?

例如:

A = set([...])
B = set([...])

print(A.difference(B)) # What is the time complexity of the difference function? 

我的直觉告诉我 O(n) 因为我们可以遍历集合 A 并且对于每个元素，查看它是否在恒定时间内包含在集合 B 中(使用哈希函数).

My intuition tells me O(n) because we can iterate through set A and for each element, see if it's contained in set B in constant time (with a hash function).

我说得对吗?

(这是我遇到的答案:https://wiki.python.org/moin/时间复杂度)

(Here is the answer that I came across: https://wiki.python.org/moin/TimeComplexity)

推荐答案

看起来你是对的，在最好的情况下以 O(n) 复杂度执行差异

looks that you're right, difference is performed with O(n) complexity in the best cases

但请记住，在最坏的情况下(最大化与散列的冲突)它可以提升到 O(n**2)(因为查找最坏的情况是 O(n)代码>:set()是如何实现的?，不过貌似一般可以依赖O(1))

But keep in mind that in worst cases (maximizing collisions with hashes) it can raise to O(n**2) (since lookup worst case is O(n): How is set() implemented?, but it seems that you can generally rely on O(1))

顺便说一句，速度取决于set中对象的类型.整数散列很好(大致和它们自己一样，可能有一些模数)，而字符串需要更多的 CPU.

As an aside, speed depends on the type of object in the set. Integers hash well (roughly as themselves, with probably some modulo), whereas strings need more CPU.

这篇关于Python中集差函数的运行时间是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！