代换法解递归式
问题描述:
代换法解递归式
证明T(n)=T(n/2)+1的解为O(lgn)
答
首先你需要知道在靠近计算机的领域lg的默认底数是2.另外你没有给出Base Case,那么我假设它是θ(1).证明如下:Assume:T(k)≤c•lgn,k≤n,c is a constant.∴T(n)=T(n/2) 1≤c•lg(n/2) 1=c•lgn-(1-1)...