给定两个集合 A 和 B 及其长度：a=len(A) 和 b=len(B)，其中 a>=b。 Python 2.7 的 issubset() 函数（即 B.issubset(A)）的复杂度是多少？我从网上找到了两个相互矛盾的答案：
1、O(a) 或 O(b)
发现自：https://wiki.python.org/moin/TimeComplexity和 bit.ly/1AWB1QU
（抱歉，我无法发布更多 http 链接，因此我必须使用缩短的 url。）
我从Python官网下载了源码，发现：
def issubset(self, other):
"""Report whether another set contains this set."""
self._binary_sanity_check(other)
if len(self) > len(other): # Fast check for obvious cases
return False
for elt in ifilterfalse(other._data.__contains__, self):
return False
return True
这里只有循环。
2、O(a*b)
发现自：bit.ly/1Ac7geK
我还发现一些代码看起来像Python的源代码，来自：bit.ly/1CO9HXa，如下所示：
def issubset(self, other):
for e in self.dict.keys():
if e not in other:
return False
return True
这里有两个循环。
那么哪一个是正确的呢？有人可以给我详细的答案关于上述两种解释之间的区别吗？非常感谢。
复杂度B.issubset(A) is O(len(B))， 假如说e in A是常数时间。
这通常是一个合理的假设，但很容易被错误的哈希函数所违反。例如，如果所有元素A具有相同的哈希码，时间复杂度为B.issubset(A)会恶化到O(len(B) * len(A)).
在第二个代码片段中，复杂性与上面相同。仔细一看，只有一个循环；另一个是if陈述 （if e not in other:).
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
