这是什么算法的运行时间? (递归杨辉三角形) [英] 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屋!