1

我有这个重复关系

T(n) = T(n-1) + n, for n ≥ 2
T(1) = 1

练习题：用迭代法求解递推关系，给出一个渐近的运行时间。

所以我这样解决了：

T(n) = T(n-1) + n 
        = T(n-2)  + (n - 1) + n 
        = T(n-3) + (n - 2) + (n - 1) + n 
        = … 
        = T(1) + 2 + … (n - 2) + (n - 1) + n **
        = 1 + 2 + … + (n - 2) + (n - 1) + n
        = O(n^2)

我有一些问题：

1）我怎样才能找到渐近运行时间？

**2) 在问题的这种状态下，T(1) 意味着存在 n，当它与一个数字相减时，结果为 1，对吗？

3) 如果 T(0) = 1 会怎样，如果 T(2) = 1 会怎样？

编辑：4）为什么n ≥ 2有用？

我真的需要为我的期中考试了解它

4

1 回答 1

2 
T(n) = T(n-1) + n, for n ≥ 2
T(1) = 1

ifT(x)代表运行时间：

您已经找到了渐近运行时间O(n^2)（二次）。

如果关系变为T(0) = 1或T(2) = 1，则运行时间仍然是二次的。如果您添加一个常数或乘以一个常数，渐近行为不会改变，并且更改初始条件只会将一个常数添加到以下项中。

n ≥ 2存在于关系中，因此T(n)对于每个正n. 否则，这两行都适用于T(1). 您无法T(1)使用T(0). T(n) = T(n-1) + n即使可以，T(1)也会以两种不同（并且可能不一致）的方式定义。

于 2012-11-17T09:59:52.050 回答