生成所有组合时的复杂性 [英] Complexity when generating all combinations

问题描述

面试问题的开头是可以通过生成数组元素的所有可能组合来解决"，通常是为了让我找到更好的东西.

Interview questions where I start with "this might be solved by generating all possible combinations for the array elements" are usually meant to let me find something better.

无论如何，我想添加我肯定会喜欢另一个解决方案，因为这是O(X)".问题是:为给定集合生成所有组合的O(X)复杂度是多少?

Anyway I would like to add "I would definitely prefer another solution since this is O(X)".. the question is: what is the O(X) complexity of generating all combinations for a given set?

我知道有n个！ /(n-k)！k！组合(二项式系数)，但是如何从中获得big-O表示法呢?

I know that there are n! / (n-k)!k! combinations (binomial coefficients), but how to get the big-O notation from that?

推荐答案

首先，使用O(n! / (n-k)!k!)-或任何其他功能f(n)作为O(f(n))并没有什么问题，但是我相信您正在寻找一种更简单的方法仍然拥有相同集合的解决方案.

First, there is nothing wrong with using O(n! / (n-k)!k!) - or any other function f(n) as O(f(n)), but I believe you are looking for a simpler solution that still holds the same set.

如果您愿意将子集k的大小视为常数，

If you are willing to look at the size of the subset k as constant,

对于k< = n-k:

for k<=n-k:

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)

But the above is actually (n^k + O(n^(k-1))) / k!, which is in O(n^k)

类似地，如果n-k<k，则得到O(n^(n-k))

Similarly, if n-k<k, you get O(n^(n-k))

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

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