很简单：解决T（N）= T（N-1）+ N的迭代 [英] Easy: Solve T(n)=T(n-1)+n by Iteration Method

问题描述

是否有人可以帮助我？

  

使用迭代的方法来解决这个问题。 T（N）= T（N-1）+ N

步骤说明将大大AP preciated。

解决方案

  T（N）= T（N-1）+ N

T（N-1）= T（N-2）+ n-1个

T（N-2）= T（N-3）+ N-2
 

等 可以替代T（N-1）和T（N-2）在T（n）的数值以获得的模式的总体构思。

  T（N）= T（N-2）+ N-1 + N


T（N）= T（N-3）+ N-2 + N-1 + N

T（N）= T（N-K）+ KN  -  K（K-1）/ 2
 

有关基本情况：

  N  -  K = 1，所以我们可以得到T（1）
 

K = N - 1 取代上述

  T（N）= T（1）+（N-1）N  - （N-1）（N-2）/ 2
 

您可以看到的是秩序的N ^ 2

Can someone please help me with this ?

Use iteration method to solve it. T(n) = T(n-1) +n

Explanation of steps would be greatly appreciated.

解决方案

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

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

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

and so on you can substitute the value of T(n-1) and T(n-2) in T(n) to get a general idea of the pattern.

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


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

T(n) = T(n-k) +kn - k(k-1)/2

For base case:

n - k =1 so we can get T(1)

k = n - 1 substitute in above

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

Which you can see is of Order n^2

这篇关于很简单：解决T（N）= T（N-1）+ N的迭代的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！