以下递归算法是一种计算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时间复杂度是多少?