以下递归算法是一种(相当低效的)计算 n 选择 k 的方法:
int combinationsOf(int n, int k) {
if (k == 0) return 1;
if (n == 0) return 0;
return combinationsOf(n - 1, k) + combinationsOf(n - 1, k - 1);
}
它基于以下递归见解:
实际上评估这个函数需要很多函数调用。例如,以这种方式计算 2 choose 2 会进行以下调用:
combinationsOf(2, 2)
| |
| +- combinationsOf(1, 2)
| | |
| | +- combinationsOf(0, 2)
| |
| +-- combinationsOf(1, 1)
| | |
| | +- combinationsOf(0, 1)
| |
| +- combinationsOf(1, 0)
+- combinationsOf(2, 1)
| |
| +- combinationsOf(2, 0)
|
+- combinationsOf(1, 1)
| |
| +- combinationsOf(0, 1)
|
+- combinationsOf(1, 0)
有很多方法可以提高这个函数的运行时间——我们可以使用动态规划,使用封闭式公式 nCk = n!/(k! (n - k)!),等等。但是,我很好奇这种特定算法的效率如何。
作为 n 和 k 的函数,此函数的大 O 时间复杂度是多少?
最佳答案
让C(n,k)
计算成本binom(n,k)
以这种方式,用
C(0,_) = 1
C(_,0) = 1
作为基本案例。
复发很明显
C(n,k) = 1 + C(n-1,k-1) + C(n-1,k)
如果我们将加法的成本设为 1。那么,我们可以很容易地检查
k
C(n,k) = 2 * ∑ binom(n,j) - 1
j=0
归纳法。
所以对于 k >= n
, 成本是 2^(n+1) - 1
, C(n,n-1) = 2^(n+1)- 3
, C(n,1) = 2*n+1
, C(n,2) = n*(n+1)+1
,(除此之外,我没有看到简洁的公式)。
我们有明显的上限
C(n,k) < 2^(n+1)
独立于k
, 以及 k < n/2
我们可以粗略估计
C(n,k) <= 2*(k+1)*binom(n,k)
这为小 k
提供了更小的边界, 所以总体而言
C(n,k) ∈ O(min{(k+1)*binom(n,min(k, n/2)), 2^n})
(需要将 k
限制为最小值,因为 binom(n,k)
对于 k > n/2
减小回 1)。
关于algorithm - 这个用于计算组合的天真代码的大 O 复杂度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16619187/