首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

求T(n)=T(n-1)+Theta(n)解决方案

2013-03-27 
求T(n)T(n-1)+Theta(n)T(n)T(n-1)+Theta(n)T(n)Theta(n^2)这个怎么证明呢[解决办法]T(n)-T(n-1) c*n

求T(n)=T(n-1)+Theta(n)
T(n)=T(n-1)+Theta(n)
T(n)=Theta(n^2)

这个怎么证明呢

求T(n)=T(n-1)+Theta(n)解决方案
[解决办法]
T(n)-T(n-1) <= c*n
T(n)-T(0) = T(n)-T(n-1) + T(n-1)-T(n-2) + ... + T(1)-T(0)
<= c*n + c*(n-1) + ... + c*1
= c*n*(n+1)/2
另一个方向同理。

热点排行