递归函数分析

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