由于以下功能：

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

什么是对运行compexity˚F？我知道如何做到这一点快速和肮脏的，但如何正确表征呢？它是 O（2 ^（M ​​ N））？

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

推荐答案

这是杨辉三角的一个实例：每一个元素是两个元素它上面的，是所有的人边的总和

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.

所以 F（N，M）=（N + M）！ /（N！：M！）。

现在知道来电的号码 F 来计算所需的 F（N，M），你可以构造一个修改帕斯卡三角。而不是以上元素的总和，考虑 1 +总和（调用本身以及两个递归调用）

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

绘制修改后的三角形，你很快就会说服自己，这正是 2.F（N，M） - 1

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

您可以获取二项式系数从斯特灵公式的渐近行为。的http://en.wikipedia.org/wiki/Binomial_coefficient#Bounds_and_asymptotic_formulas

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)