生成所有组合时的复杂性

Question

面试问题我开始说"这可能通过为数组元素生成所有可能的组合来解决"通常意味着让我找到更好的东西.

无论如何,我想补充"我肯定更喜欢另一种解决方案,因为这是O(X)"..问题是:为给定集合生成所有组合的O(X)复杂度是多少？

我知道有n!/(nk)!k!组合(二项式系数),但如何从中得到大O符号？

Answer 1

首先,没有什么错误使用O(n! / (n-k)!k!)-或任何其他功能f(n)作为O(f(n)),但我相信你正在寻找仍持有相同的一组简单的解决方案.

如果您愿意将子集的大小k视为常量,

对于k <= nk:

n! / ((n-k)!k!) = ((n-k+1) (n-k+2) (n-k+3) ... n ) / k! 

但实际上(n^k + O(n^(k-1))) / k!,上面是O(n^k)

同样,如果n-k<k,你得到O(n^(n-k))

这给了我们 O(n^min{k,n-k})

Answer 2

我知道这是一个老问题，但它是谷歌上的热门话题，恕我直言，有一个错误标记的接受答案。

C(n,k) = n Choose k = n! / ( (n-k)! * k!)

上面的函数表示可以由一组 n 元素组成的 k 元素集的数量。纯粹从逻辑推理的角度来看，C(n, k)必须小于

? C(n,k) ? k ? (1..n).

因为这个表达式代表幂集。在英语中，上述表达式代表：add C(n,k) for all k from 1 to n。我们知道这是有2 ^ n元素的。

因此，C(n, k)的上限2 ^ n肯定小于n ^ kany n, k > 3, and k < n。

所以回答你的问题肯定C(n, k)有一个上限2 ^ n，但不知道是否有一个更严格的上限来更好地描述它。

Answer 3

作为 @amit 的后续， 的上限min{k, n - k}是n / 2。

因此，“n 选择 k”复杂度的上限为O(n ^ (n / 2))