recursion - 递归函数分析

Question

我正在尝试分析我编写的递归程序的性能。

基本代码是

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

我想为对 Cost() 的调用次数写一个递归关系。我该如何开始呢？

类似的东西T(x) = T(x/2)。但我不认为这是正确的

编辑：对于对 Cost() 的 3 个递归调用，我可以将其表示为分支因子为 3 的树。那么它会更准确T(x) = T(x/3)吗？

Answer 1

你真的写了一个递归解决方案吗？（我希望它是一个与线性迭代进行比较的任务）

我想

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

Answer 2

对 Cost() 的调用次数为：

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

因此，对于输入x， Cost() 被调用一次加上它被调用的次数x-1、x-2和x-3。这是假设您的解决方案不使用记忆。递归关系并不漂亮：http ://www.wolframalpha.com/input/?i=T(x)+%3D+1+%2B+T(x-1)+%2B+T(x-2 )+%2B+T(x-3)

然而，使用 memoization，你的“调用次数”变成了C(x) = x因为你只需要在and之间进行C(i)一次评估。（可能是，取决于您的初始条件）i0xC(x) = x + 1