这个天真的代码计算组合的大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)

它给小的一个小得多k,所以整体

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

(需要k将最小值钳位,因为binom(n,k)减少到1 k > n/2).