这个天真的代码计算组合的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时间复杂度是多少？

评论
  • lillo
    lillo 回复
    O(2^n)

    当n k，则通过命中k = 0停止递归操作，k的步数少于n = 0，但是总体复杂度仍为2 ^ n。

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

  • luyao
    luyao 回复

    Let C(n,k) be the cost of computing binom(n,k) in that way, with

    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

    通过归纳。

    So for k >= n, the cost is 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, (and beyond that, I don't see neat formulae).

    我们有明显的上限

    C(n,k) < 2^(n+1)

    independent of k, and for k < n/2 we can coarsely estimate

    C(n,k) <= 2*(k+1)*binom(n,k)

    which gives a much smaller bound for small k, so overall

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

    (need to clamp the k for the minimum, since binom(n,k) decreases back to 1 for k > n/2).