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

Question

以下递归算法是一种(相当低效的)计算 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 时间复杂度是多少？

Answer 1

让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)。