求T(n)=T(n-1)+Theta(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) <= 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
另一个方向同理。
T(n)=T(n-1)+Theta(n)
T(n)=Theta(n^2)
这个怎么证明呢
------解决方案--------------------
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
另一个方向同理。