遞歸函數分析

Question

我試圖分析我寫的遞歸程序的性能。

的基本代碼是

Cost(x) 
{ 
1 + MIN(Cost(x-1), Cost(x-2), Cost(x-3)) 
} 

我想寫作出成本呼叫的次數遞歸關係（）。我將如何開始這個？

類似T(x) = T(x/2)。但我不認爲這是正確的

編輯：我可以表示這是一個分支因子爲3的樹，對Cost（）的3次遞歸調用中的每一個。那麼它會更準確地是T(x) = T(x/3)？

Answer 1

做出成本（呼叫數）爲：？

C(x) = 1 + C(x-1) + C(x-2) + C(x-3) 

因此，對於輸入x，成本（）被調用一次，再加上它被稱爲爲x-1的倍量，x-2和x-3。這是假設您的解決方案不使用memoization。遞推關係並不漂亮：http://www.wolframalpha.com/input/?i=T(x)+%3D+1+%2B+T(x-1)+%2B+T(x-2)+%2B+T(x-3)

使用記憶化，但是，你的「呼叫次數」變成C(x) = x因爲你只需要一次0和x之間的所有i評估C(i)。 （可能是C(x) = x + 1，取決於你的初始條件）

Answer 2

你真的寫一個遞歸解決方案（我希望它是一個任務來比較線性迭代）

我覺得

T(X) = T(X-1)+T(X-2)+T(X-3)+C 
C is small constant