如何用迭代法求解T(n)=T(n-1)+ (n-1)？

Question

谁能帮我解决这个问题：使用迭代方法求解 T (n) = T (n - 1) + (n - 1)

并证明T(n)∈Θ(n²)

拜托，如果你能一步一步解释一下，我将不胜感激。

Answer 1

T(n) = T(n - 1) + (n - 1)
      = (T(n - 2) + (n - 2)) + (n - 1)
      = (T(n - 3) + (n - 3)) + (n - 2) + (n - 1)
      = ...
      = T(0) + 1 + 2 + ... + (n - 3) + (n - 2) + (n - 1)
      = C + n * (n - 1) / 2
      = O(n²)

因此对于足够大的n，我们有：

n * (n - 1) / 3 ≤  T(n) ≤ n²

因此我们有T(n) = Ω(n²) and T(n) = O(n²)，因此T(n) = Θ (n²)。

Answer 2

我用一个简单的方法解决了:

T (n) = T (n - 1) + (n - 1)-----------(1)
//now submit T(n-1)=t(n)

T(n-1)=T((n-1)-1)+((n-1)-1)
T(n-1)=T(n-2)+n-2---------------(2)

now submit (2) in (1) you will get
i.e T(n)=[T(n-2)+n-2]+(n-1)
T(n)=T(n-2)+2n-3 //simplified--------------(3)

now, T(n-2)=t(n)
 T(n-2)=T((n-2)-2)+[2(n-2)-3]
T(n-2)=T(n-4)+2n-7---------------(4)
now submit (4) in (2) you will get
i.e T(n)=[T(n-4)+2n-7]+(2n-3)
T(n)=T(n-4)+4n-10 //simplified
............
T(n)=T(n-k)+kn-10

now, assume k=n-1

T(n)=T(n-(n-1))+(n-1)n-10
T(n)=T(1)+n^2-n-10
According to the complexity 10 is constant

So , Finally O(n^2)

Answer 3

T(n)-T(n-1) = n-1 T(n-1)-T(n-2) = n-2

相减

T(n)-2T(n-1)+T(n-2) = 1 T(n-1)-2T(n-2)+T(n-3) = 1

同样，通过替换

T(n)-3T(n-1)+3T(n-2)-T(n-3) = 0

递归的特征方程为

x^3-3x^2+3x-1 = 0

或

(x-1)^3 = 0.

它有根 x_1,2,3 = 1,

所以递归的一般解是

T(n) = C_1 1^n + C_2 n 1^n + C_3 n^2 1^n

或

T(n) = C_1 + C_2 n + C_3 n^2.

所以，

T(n) = Θ(n^2)。

如何用迭代法求解T(n)=T(n-1)+ (n-1)？

How to solve T(n)=T(n-1)+ (n-1) by Iteration Method?

iteration

algorithm

recursion

recurrence

time-complexity