作者JKLee (J.K.Lee)
看板Grad-ProbAsk
标题[理工] [资结][分享] C(n,k) 递回函数 呼叫次数
时间Thu Dec 21 01:00:15 2017
考虑以下计算二项式系数(binomial coefficient)的C程式码：
int C(int n, int k)
{
if(n == k || k == 0 )
return 1;
else
return C(n-1, k) + C(n-1, k-1);
}
令 T(n,k) 为计算 C(n,k) 的过程中，呼叫函数 C 的次数。
则 T(n,k) =
1 , if n = k or k = 0 ; -----(1)
T(n-1, k) + T(n-1, k-1) + 1 , otherwise. -----(2)
以下提供一种方法求出 T(n,k) 的 closed form。
方法为把 T(n,k) 的递回关系(2)与初始条件(1)调整到与 C(n,k) 的相同。
C(n,k) 的初始条件与递回关系如下：
C(n,k) =
1 , if n = k or k = 0 ; -----(3)
C(n-1, k) + B(n-1, k-1) , otherwise. -----(4)
首先把 T(n,k) 的递回关系调整到与 C(n,k) 相同。
令 U(n,k) = T(n,k) + 1 。
If n = k or k = 0, then
U(n,k) = 2. -----(5)
Otherwise,
U(n,k) = T(n-1, k) + 1 + T(n-1, k-1) + 1
= U(n-1, k) + U(n-1, k-1) . -----(6)
U(n,k) 的递回关系(6)已经与 C(n,k) 相同。
接者，在不改变递回关系的条件下，把 U(n,k) 的初始条件(5)调整到与 C(n,k) 相同。
令 V(n,k) = 1/2 * U(n,k)。
If n = k or k = 0, then
V(n,k) = 1. -----(7)
Otherwise,m
V(n,k) = 1/2 * U(n-1, k) + 1/2 * U(n-1, k-1)
= V(n-1, k) + V(n-1, k-1) . -----(8)
至此，V(n,k) 已与 C(n,k) 相同，因为两个函数的递回关系与初始条件都一样。
又 V(n,k) = 1/2 * U(n,k) = 1/2 * [T(n,k) + 1]
所以，计算 C(n,k) 的过程中，呼叫函数 C 的次数为
T(n,k) = 2 * C(n,k) - 1
或是写成
T(n,k) = 2 * n!/[k!*(n-k)!] - 1
---
用类似的方法，也可以推出阿克曼(Ackermann)函数的呼叫次数，不过考试应该不会考:P
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 61.231.155.137
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1513789218.A.785.html
1F：推 kobebset105: 感谢大大分享～12/21 11:15
2F：推 twps6106: 感谢分享12/21 12:25
3F：推 winiel559: Pretty cool, thanks12/21 13:09
4F：推 s89162504: 今年中山就考了 QQ12/21 14:07
有考Ackermann函数的呼叫次数？
看起来只有考Ackermann函数的值而已。
而且扫描品质很差劲，A(4,1)印成A(1,1)。
5F：推 FRAXIS: 其实我觉得不用想那麽复杂吧 因为 base case 只有 112/21 16:31
6F：→ FRAXIS: 所以 recursion tree 的 leaves 一定是 C(n, k) 个12/21 16:32
帮补充: 由递回关系可知，recursion tree 是 strict binary tree
7F：→ FRAXIS: 然後加上 internal node 有 C(n, k) - 1 个12/21 16:32
推F大
※ 编辑: JKLee (61.231.155.137), 12/22/2017 10:09:53