我们知道这个问题是np-完全的,因此,找不到多项式算法.同样,我们知道集合中所有分区的数量等于响铃的数量.我看到很少有算法可以生成集合的所有分区,但是找不到解决该问题的时间复杂度.
We know that this problem is np-complete, hence, no polynomial algorithm can be found for it. Also, we know that number of all partitions of a set is equal to the bell's number. I see there are few algorithms to generate all partitions of a set but couldn't find what is the time complexity to solve this problem.
例如,此python代码以递归方式生成集合的所有分区.该算法的时间复杂度是多少?能否以更好的时间复杂度解决此问题?
For example, this python code generates all partitions of a set recursively. What is the time complexity of this algorithm? Could this problem be solved with better time complexity?
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 推荐答案首先,请注意,此问题不是 NP -完整的. NP 是一类决策问题,但不是.通常,区别是无用的语义,但是在这种情况下,没有明显的大致等效的决策问题.此外,对于要在 NP 中出现的问题,答案必须是可在多项式时间内验证的,并且对于 NP -困难,必须为该问题提供O(1)的预言 NP 中的其他问题需要在多项式时间内解决.都不是这种情况.
First off, note that this problem is not NP-complete. NP is a class of decision problems, which this problem is not. Often the distinction is useless semantics, but in this case there is no clear roughly equivalent decision problem. Furthermore, for a problem to be in NP the answer has to be verifiable in polynomial time, and to be NP-hard an O(1) oracle for the problem must allow other problems in NP to be solved in polynomial time. Neither of these is the case.
话虽如此,您正确地说一组大小为 n 的分区的数量等于第n个Bell编号.现在,由于您的代码不需要搜索分区,因此它给出了分区每一步",因此按与Bell数成比例的时间运行.从技术上讲,还有一个多项式项,因为较大的分区需要更长的时间才能生成,但是该项将占主导地位.
That having been said, you rightly say that the number of partitions of a set of size n is equal to the n'th Bell number. Now, because your code requires no search for partitions, it gives a partition "every step", and thus runs in time proportional to the Bell number. Technically there is also a polynomial term as larger partitions take longer to generate, but this term will be dominated.
那么,贝尔数字的大数字是什么?事实证明,这个问题很难回答.维基百科提到了贝尔数字的一些上限,其中一个在2010年发现((0.792n/ln(n + 1))^ n),但似乎没有严格的证明.
What, then, is the big-o for the Bell numbers? This question turns out to be somewhat difficult to answer. Wikipedia mentions some upper bounds for Bell numbers, one of them found in 2010 ((0.792n / ln(n+1))^n), but there does not appear to be a tight bound proven.
更多推荐
查找集合中所有分区的时间复杂度
发布评论