以下递归算法是一种计算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选择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的函数的big-O时间复杂度是多少?
当n k,则通过命中k = 0停止递归操作,k的步数少于n = 0,但是总体复杂度仍为2 ^ n。
但是真正的问题是递归本身-您很快就会达到堆栈限制。
Let
C(n,k)
be the cost of computingbinom(n,k)
in that way, with作为基本案例。
复发明显
如果我们用加法得到成本1。那么,我们可以轻松地检查
通过归纳。
So for
k >= n
, the cost is2^(n+1) - 1
,C(n,n-1) = 2^(n+1)- 3
,C(n,1) = 2*n+1
,C(n,2) = n*(n+1)+1
, (and beyond that, I don't see neat formulae).我们有明显的上限
independent of
k
, and fork < n/2
we can coarsely estimatewhich gives a much smaller bound for small
k
, so overall(need to clamp the
k
for the minimum, sincebinom(n,k)
decreases back to 1 fork > n/2
).