简单:通过迭代法求解 T(n)=T(n-1)+n [英] Easy: Solve T(n)=T(n-1)+n by Iteration Method
本文介绍了简单:通过迭代法求解 T(n)=T(n-1)+n的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
有人可以帮我解决这个问题吗?
Can someone please help me with this ?
用迭代法求解. T(n) = T(n-1) +n
Use iteration method to solve it. T(n) = T(n-1) +n
非常感谢您解释步骤.
推荐答案
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) 中以大致了解该模式.
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 ...(1)
对于基本情况:
n - k = 1 so we can get T(1)
=> k = n - 1
代入(1)
=> k = n - 1
substitute in (1)
T(n) = T(1) + (n-1)n - (n-1)(n-2)/2
你可以看到的顺序是 n2 => O(n2).
Which you can see is of Order n2 => O(n2).
这篇关于简单:通过迭代法求解 T(n)=T(n-1)+n的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文