[理工] [資結][分享] C(n,k) 遞迴函數 呼叫次數

[JKLee (J.K.Lee)]

考慮以下計算二項式係數(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://www.ptt.cc/bbs/Grad-ProbAsk/M.1513789218.A.785.html
推 kobebset105: 感謝大大分享～
推 twps6106: 感謝分享
推 winiel559: Pretty cool, thanks
推 s89162504: 今年中山就考了 QQ
有考Ackermann函數的呼叫次數？

看起來只有考Ackermann函數的值而已。

而且掃描品質很差勁，A(4,1)印成A(1,1)。

推 FRAXIS: 其實我覺得不用想那麼複雜吧 因為 base case 只有 1
→ FRAXIS: 所以 recursion tree 的 leaves 一定是 C(n, k) 個
幫補充: 由遞迴關係可知，recursion tree 是 strict binary tree

→ FRAXIS: 然後加上 internal node 有 C(n, k) - 1 個
推F大
※ 編輯: JKLee (61.231.155.137), 12/22/2017 10:09:53