算法导论第七章的一道证明题如何利用代换法证明T(n)T(n-1)+theta(n)的解是T(n)theta(n^2)?[解决办法]式
算法导论第七章的一道证明题
如何利用代换法证明
T(n)=T(n-1)+theta(n)的解是T(n)=theta(n^2)?
[解决办法]
式子应当理解成c1*n<=T(n)-T(n-1)<=c2*n
然后加起来就变成c1*(1+2+...+n)<=T(n)-T(0)<=c2*(1+2+...*n)
算法导论第七章的一道证明题
如何利用代换法证明
T(n)=T(n-1)+theta(n)的解是T(n)=theta(n^2)?
[解决办法]
式子应当理解成c1*n<=T(n)-T(n-1)<=c2*n
然后加起来就变成c1*(1+2+...+n)<=T(n)-T(0)<=c2*(1+2+...*n)