What is the runtime of this algorithm? (Recursive

问题:

Given the following function:

Function f(n,m)
   if n == 0 or m == 0: return 1
   return f(n-1, m) + f(n, m-1)

What's the runtime compexity of f? I understand how to do it quick and dirty, but how to properly characterize it? Is it O(2^(m*n))?

回答1:

This is an instance of Pascal's triangle: every element is the sum of the two elements just above it, the sides being all ones.

So f(n, m) = (n + m)! / (n! . m!).

Now to know the number of calls to f required to compute f(n, m), you can construct a modified Pascal's triangle: instead of the sum of the elements above, consider 1 + sum (the call itself plus the two recursive calls).

Draw the modified triangle and you will quickly convince yourself that this is exactly 2.f(n, m) - 1.

You can obtain the asymptotic behavior of the binomial coefficients from Stirling's approximation. http://en.wikipedia.org/wiki/Binomial_coefficient#Bounds_and_asymptotic_formulas

f(n, m) ~ (n + m)^(n + m) / (n^n . m^m)

回答2:

The runtime of f(n, m) is in O(f(n, m)). This is easily verified by the following observation:

Function g(n, m):
    if n=0 or m=0: return 1
    return g(n-1, m) + g(n, m-1) + 1

The function f is called equally often as g. Furthermore, the function g is called exactly g(n, m) times to evaluate the result of g(n, m). Likewise, the function f is called exactly g(n, m) = 2*f(n, m)-1 times in order to evaluate the result of f(n, m).

As @Yves Daoust points out in his answer, f(n, m) = (n + m)!/(n!*m!), therefore you get a non-recursive runtime of O((n+m)!/(n!*m!)) for f.

回答3:

Understanding the Recursive Function

f(n, 0) = 1
f(0, m) = 1
f(n, m) = f(n - 1, m) + f(n, m - 1)

The values look like a Pascal triangle to me:

   n 0  1  2  3  4 ..
 m

 0   1  1  1  1  1 ..
 1   1  2  3  4
 2   1  3  6
 3   1  4     .
 4   1           .
 .   .
 .   .

Solving the Recursion Equation

The values of Pascal's triangle can be expressed as binomial coefficients. Translating the coordinates one gets the solution for f:

f(n, m) = (n + m) 
          (  m  )
        = (n + m)! / (m! (n + m - m)!) 
        = (n + m)! / (n! m!)

which is a nice term symmetric in both arguments n and m. (Final term first given by @Yves Daoust in this discussion)

Pascal's Rule

The recursion equation of f can be derived by using the symmetry of the binomial coefficients and Pascal's Rule

f(n, m) = (n + m)
          (  n  )
        = (n + m)
          (  m  )
        = ((n + m) - 1) + ((n + m) - 1)
          (      m    )   (    m - 1  )
        = ((n - 1) + m) + (n + (m - 1))
          (     m     )   (    m      )
        = f(n - 1, m) + f(n, m - 1)

Determing the Number of Calls

The "number of calls of f" calculation function F is similar to f, we just have to add the call to f itself and the two recursive calls:

F(0, m) = F(n, 0) = 1, otherwise

F(n, m) = 1 + F(n - 1, m) + F(n, m - 1)

(Given first by @blubb in this discussion).

Understanding the Number of Calls Function

If we write it down, we get another triangle scheme:

 1  1  1  1  1 ..
 1  3  5  7
 1  5 11
 1  7     .
 1           .
 .
 .

Comparing the triangles value by value, one guesses

F(n, m) = 2 f(n, m) - 1  (*)

(Result first suggested by @blubb in this discussion)

Proof

We get

F(0, m) = 2 f(0, m) - 1  ; using (*)
        = 1              ; yields boundary condition for F 

F(n, 0) = 2 f(n, 0) - 1 
        = 1

as it should and examining the otherwise clause, we see that

F(n, m) = 2 f(n, m) - 1                                   ; assumption
        = 2 ( f(n - 1, m) + f(n, m - 1) ) - 1             ; definition f
        = 1 + (2 f(n - 1, m) - 1) + (2 f(n, m - 1) - 1)   ; algebra
        = 1 + F(n - 1, m) + F(n, m - 1)                   ; 2 * assumption

Thus if we use (*) and the otherwise clause for f, the otherwise clause for F results.

As the finite difference equation and the start condition for F hold, we know it is F (uniqueness of the solution).

Estimating the Asymptotic Behaviour of the Number of Calls

Now on calculating / estimating the values of F (i.e. the runtime of your algorithm).

As

F = 2 f - 1

we see that

O(F) = O(f).

So the runtime of this algorithm is

O( (n + m)! / (n! m!) )

(Result first given by @Yves Daoust in this discussion)

Approximating the Runtime

Using the Stirling approximation

n! ~= sqrt(2 pi n) (n / e)^n

one can get a form without hard to calculate factorials. One gets

f(n, m) ~= 1/(2 pi) sqrt((n+m) / (n m)) [(n + m)^(n + m)] / (n^n m^m)

thus arriving at

O( sqrt((n + m) / (n m)) [(n + m)^(n + m)] / (n^n m^m) )

(Use of Stirling's formula first suggested by @Yves Daoust in this discussion)