首先，请注意，此问题不是 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.