这个算法的运行时间是什么？（递归帕斯卡三角形）

Question

给定以下函数：

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

f 的运行时复杂度是什么？我知道如何快速脏乱地完成它，但如何正确地描述它？它是 O(2^(m*n)) 吗？

- user3219632

---

你确定它不是2^(m+n)吗？ - mbeckish

@RonTeller - 大O符号忽略常数，因此如果运行时间实际上是2^(m+n)+1或类似的情况，在大O符号中仍然是O(2^(m+n))。 - mbeckish

@RonTeller - 你说得对。blubb 给出了正确的答案。 - mbeckish

@amink - 我认为它只是一个深度为min(m,n)的完全二叉树。之后，树会变得更加稀疏。最长的分支长度将为m + n。 - mbeckish

这个链接可能会回答你的问题：http://math.stackexchange.com/questions/80582/solving-recursion-with-2-parameters - Mohamed Ennahdi El Idrissi

Answer 1

这是一个帕斯卡三角形示例：每个元素都是其上方两个元素之和，两侧均为1。

因此，f(n, m) = (n + m)! / (n! . m!)。

现在，要知道计算f(n, m)所需调用的f函数次数，可以构造一个修改过的帕斯卡三角形：不考虑上方元素的总和，而是考虑1 + sum（调用本身加上两个递归调用）。

画出修改后的三角形，您很快就会发现这正是2.f(n, m) - 1。

您可以通过斯特林近似法获得二项式系数的渐近行为。

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

- user1196549

Answer 2

f(n, m)的运行时间为O(f(n, m))。这可以通过以下观察轻松验证：

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

函数f被调用的次数与函数g相等。此外，为了计算g(n, m)的结果，函数g会被调用g(n, m)次。同样地，为了计算f(n,m)的结果，函数f会被调用g(n,m) = 2*f(n,m)-1次。

正如@Yves Daoust在他的答案中指出的那样，f(n,m) = (n + m)!/(n!*m!)，因此您可以获得f的非递归运行时间为O((n+m)!/(n!*m!))。

- blubb

---

不确定第二部分：假设 n=10 m=1，你的函数返回2 (应该是 2*f)，而原始函数将返回 11。 - Ron Teller

现在它会返回“3”，这仍然是错误的。 - Ron Teller

@RonTeller：我修改了我的答案，现在应该是正确的。 - blubb

Answer 3

理解递归函数

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）

- mvw