这个天真的代码计算组合的big-O复杂度是多少？

由 发布于 algorithmmathcombinationsbig-o
 收藏

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