Python的复杂性issubset() [英] The complextiy of Python issubset()

问题描述

给出两个集合A和B及其长度:a = len(A)和b = len(B)其中a> = b. Python 2.7的issubset()函数(即B.issubset(A))的复杂性是什么?我可以从互联网上找到两个矛盾的答案:

Given two sets A and B and their length: a=len(A) and b=len(B) where a>=b. What is the complextiy of Python 2.7's issubset() function, ie, B.issubset(A)? There are two conflicting answers I can find from the Internet:

1，O(a)或O(b)

1, O(a) or O(b)

发现于: https://wiki.python.org/moin/TimeComplexity 和bit.ly/1AWB1QU

found from:https://wiki.python.org/moin/TimeComplexity and bit.ly/1AWB1QU

(很抱歉，我无法发布更多的http链接，所以我必须改用缩短网址.)

(Sorry that I can not post more http links so I have to use shorten url instead.)

我从Python官方网站下载了源代码，发现:

I downloaded the source code from Python offical website and found that:

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)

2, O(a*b)

发现于:bit.ly/1Ac7geK

found from: bit.ly/1Ac7geK

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

I also found some codes look like source codes of Python from: bit.ly/1CO9HXa as following:

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

这里有两个循环.

那么哪个是对的?有人能给我详细回答以上两种解释之间的区别吗?预先感谢.

So which one is right? Could someone give me a detailed answer about the difference between the above two explanations? Great thanks in advance.

推荐答案

B.issubset(A)的复杂度为O(len(B)) ，假设e in A是恒定时间.

The complexity of B.issubset(A) is O(len(B)), assuming that e in A is constant-time.

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

This a reasonable assumption generally, but can be easily violated with a bad hash function. If, for example, all elements of A had the same hash code, the time complexity of B.issubset(A) would deteriorate to O(len(B) * len(A)).

在第二个代码段中，复杂度与上面相同.如果仔细观察，只有一个循环.另一个是if语句(if e not in other:).

In your second code snippet, the complexity is the same as above. If you look closely, there is only one loop; the other is an if statement (if e not in other:).

这篇关于Python的复杂性issubset()的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！