我正在尝试分析我编写的递归程序的性能。
基本代码是
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)吗？
问问题
250 次
2 回答
0
你真的写了一个递归解决方案吗？（我希望它是一个与线性迭代进行比较的任务）
我想
T(X) = T(X-1)+T(X-2)+T(X-3)+C
C is small constant
于 2012-04-13T04:44:17.260 回答
0
对 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
于 2012-04-13T05:00:10.723 回答