如何T(n) = T(n-1) + n使用迭代方法解决，答案是theta(n^2)
问问题
4326 次
2 回答
7
T(n) = T(n-1) + n = T(n-2) + n-1 + n = ... = 1+ 2 + ... + n = (n+1)n/2 = theta(n^2)
注意假设 T(0) = 0 （你必须有递归的基础）
希望你的意思
于 2011-03-20T12:14:08.720 回答
1
有时，您还可以使用特征方程法来求解递推关系。这涉及确定特定积分和总解。
更多信息在这里：解决递归关系
于 2011-03-20T15:07:15.030 回答