面试问题的开头是“可以通过生成数组元素的所有可能组合来解决”，通常是为了让我找到更好的方法。
无论如何，我想添加“我肯定会喜欢另一个解决方案，因为这是O（X）”。问题是：为给定集合生成所有组合的O（X）复杂度是多少？
我知道那里有n！/（nk）！k！组合（二项式系数），但是如何从中获得big-O表示法呢？
首先，没有什么错误使用O(n! / (n-k)!k!)-或任何其他功能f(n)作为O(f(n))，但我相信你正在寻找仍持有相同的一组简单的解决方案。
O(n! / (n-k)!k!)
f(n)
O(f(n))
如果您愿意将子集的大小k视为常数，
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 + O(n^(k-1))) / k!
O(n^k)
同样，如果n-k<k得到，O(n^(n-k))
n-k<k
O(n^(n-k))
这给了我们 O(n^min{k,n-k})
O(n^min{k,n-k})
