python - Python的复杂度是subset()

Question

给定两个集合 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

我还发现一些代码看起来像来自 bit.ly/1CO9HXa 的 Python 源代码，如下所示:

def issubset(self, other):
    for e in self.dict.keys():
        if e not in other:
            return False
        return True

这里有两个循环

那么哪个是对的呢？有人可以就上述两种解释之间的区别给我一个详细的答案吗？非常感谢。

Answer 1

B.issubset(A)的复杂度是O(len(B))，假设e in A 是常数时间。

这通常是一个合理的假设，但很容易被错误的哈希函数所违反。例如，如果 A 的所有元素都具有相同的哈希码，则 B.issubset(A) 的时间复杂度将恶化为 O(len(B ) * len(A)).

在您的第二个代码片段中，复杂性与上述相同。如果仔细观察，只有一个循环；另一个是 if 语句(if e not in other:)。