理解递归函数
f(n, 0) = 1
f(0, m) = 1
f(n, m) = f(n - 1, m) + f(n, m - 1)
对我来说,这些值看起来像帕斯卡三角形:
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 .
. .
. .
解决递归方程
Pascal三角形的值可以表示为二项式系数。将坐标进行转换,即可得到f的解:
f(n, m) = (n + m)
( m )
= (n + m)! / (m! (n + m - m)!)
= (n + m)! / (n! m!)
这是一个在参数n和m中对称的美好术语。(最初由@Yves Daoust在此讨论中提出的最终术语)
帕斯卡定理
通过使用二项式系数的对称性和帕斯卡定理,可以推导出f的递归方程。
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)
确定调用次数
“函数f的调用次数”计算函数F与f类似,我们只需要添加对f本身和两个递归调用的调用即可:
F(0, m) = F(n, 0) = 1, otherwise
F(n, m) = 1 + F(n - 1, m) + F(n, m - 1)
(由@blubb在此讨论中首先提出)。
理解调用函数的次数
如果我们把它写下来,我们得到另一个三角形方案:
1 1 1 1 1 ..
1 3 5 7
1 5 11
1 7 .
1 .
.
.
通过逐个比较三角形的值,人们猜测
F(n, m) = 2 f(n, m) - 1 (*)
(此结果由@blubb在本讨论中首先建议)
证明
我们得到
F(0, m) = 2 f(0, m) - 1 ; using (*)
= 1 ; yields boundary condition for F
F(n, 0) = 2 f(n, 0) - 1
= 1
按照预期运行并检查否则子句,我们可以看到
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
因此,如果我们对f使用(*)和otherwise子句,则F的otherwise子句将产生结果。
由于有限差分方程和F的起始条件成立,我们知道它是F(解的唯一性)。
估计调用次数的渐近行为
现在开始计算/估计F的值(即算法的运行时间)。
如
F = 2 f - 1
我们看到
O(F) = O(f).
因此,该算法的运行时间为
O( (n + m)! / (n! m!) )
(本讨论中首先由@Yves Daoust给出结果)
近似运行时间
使用斯特林逼近。
n! ~= sqrt(2 pi n) (n / e)^n
可以在不需要计算阶乘的情况下得到一个表单。人们会得到
f(n, m) ~= 1/(2 pi) sqrt((n+m) / (n m)) [(n + m)^(n + m)] / (n^n m^m)
因此到达
O( sqrt((n + m) / (n m)) [(n + m)^(n + m)] / (n^n m^m) )
(在此讨论中首次建议使用斯特林公式的是@Yves Daoust)