查找集合的所有分区的时间复杂度

Question

我们知道这个问题是np-complete的，因此找不到多项式算法。另外，我们知道一组的所有分区的数量等于钟的数量。我看到很少有算法可以生成一个集合的所有分区，但找不到解决这个问题的时间复杂度。

例如，这段 python 代码递归地生成集合的所有分区。这个算法的时间复杂度是多少？这个问题可以用更好的时间复杂度来解决吗？

def partition(collection):
    global counter
    if len(collection) == 1:
        yield [collection]
        return
    first = collection[0]
    for smaller in partition(collection[1:]):
        for n, subset in enumerate(smaller):
            yield smaller[:n] + [[first] + subset] + smaller[n + 1:]
        yield [[first]] + smaller

Answer 1

首先，请注意这个问题不是 NP 完全的。 NP是一个class的决策问题，而这个问题不是。通常区分是无用的语义，但在这种情况下没有明确的大致等效的决策问题。此外，对于 NP 中的问题，答案必须在多项式时间内可验证，并且 NP-hard O(1)该问题的 oracle 必须允许 NP 中的其他问题在多项式时间内解决。这两种情况都不是。

话虽如此，你说得对，一组大小为n的分区数等于第n个贝尔数。现在，因为您的代码不需要搜索分区，所以它“每一步”都给出一个分区，因此运行时间与贝尔数成正比。从技术上讲，还有一个多项式项，因为较大的分区需要更长的时间来生成，但是这个项将占主导地位。

那么，贝尔数字的大 O 是什么？这个问题原来有点难以回答。 Wikipedia 提到了贝尔数的一些上限，其中之一是在 2010 年发现的 ((0.792n / ln(n+1))^n)，但似乎没有证明严格的界限。

查找集合的所有分区的时间复杂度

Time Complexity of finding all partitions of a set

python

algorithm

big-o

set

time-complexity