这是什么算法的运行时间？ （递归杨辉三角形） [英] What is the runtime of this algorithm? (Recursive Pascal's triangle)

问题描述

由于以下功能：

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)

这篇关于这是什么算法的运行时间？ （递归杨辉三角形）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！