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 选择 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)

这给 small 的界限要小得多k，所以总体而言

C(n,k) ∈ O(min{(k+1)*binom(n,min(k, n/2)), 2^n})

（需要将 钳制k为最小值，因为binom(n,k)减少回 1 k > n/2）。

Answer 2

O(2^n)

当 n<k 时，您通过在 n 步后点击 n=0 来停止递归。在每个递归级别中，您调用两个函数，所以这就是数字 2 的来源。如果 n>k 则“右分支”中的递归通过点击 k=0 停止，这比点击 n=0 的步骤少，但总体复杂度仍然为 2^n。

但真正的问题是递归本身——你很快就会达到堆栈限制。