What is the big-O complexity of this naive code to

问题:

The following recursive algorithm is a (fairly inefficient) way to compute n choose 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);
}

It is based on the following recursive insight:

Actually evaluating this function takes a LOT of function calls. For example, computing 2 choose 2 this way makes these calls:

 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)

There are many ways to improve the runtime of this function - we could use dynamic programming, use the closed-form formula nCk = n! / (k! (n - k)!), etc. However, I am curious just how inefficient this particular algorithm is.

What is the big-O time complexity of this function, as a function of n and k?

回答1:

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

C(0,_) = 1
C(_,0) = 1

as base cases.

The recurrence is obviously

C(n,k) = 1 + C(n-1,k-1) + C(n-1,k)

if we take addition to have cost 1. Then, we can easily check that

             k
C(n,k) = 2 * ∑ binom(n,j) - 1
            j=0

by induction.

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).

We have the obvious upper bound of

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).

回答2:

O(2^n)

When n<k you stop the recursion by hitting n=0 after n steps. In each level of recursion you call two functions, so this is where the number 2 came from. If n>k then the recursion in the "right branch" is stopped by hitting k=0 which is fewer steps then hitting n=0, but overall complexity is still 2^n.

But the real problem is the recursion itself - you will hit stack limit really soon.