algorithm - 生成所有组合时的复杂性

Question

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

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

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

Answer 1

首先，使用O(n! / (n-k)!k!)没有错- 或任何其他功能 f(n)作为O(f(n)) ，但我相信您正在寻找一个更简单的解决方案，该解决方案仍然包含相同的集合。

如果你愿意看子集的大小k作为常量，然后对于 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) 中

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

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