代换法解递归式证明T(n)=T(n/2)+1的解为O(lgn)

来源：学生作业帮编辑：拍题作业网作业帮分类：数学作业时间：2024/05/12 15:43:16

代换法解递归式
证明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)
∴T(n)≤c•lgn
T(1)=c•lg1 1=1
∴T(n)=O(lgn)
Wwwww

代换法解递归式证明T(n)=T(n/2)+1的解为O(lgn) T(n)=4T(n/2)+n^2/lgn 求时间复杂度证明lg（M*N）=lgM+lgN；lg（M/N）=lgM-lgN 2lg[1/2(m-n)]=lgm+lgn,求m/n的值已知2lg[1/2(m-n)]=lgm+lgn,求m/n的值?/ T N T O 已知数列{An}的前n项和为Sn=(n+1)2+t,证明:{An}成等差数列的充要条件是t=-1 m^(lgn)=n^(lgm) 设T为数域P上n维线性空间V的一个线性变换,且T^2=I.证明：1.T特征值只能为1或-1; lgM+lgN=2lg(M-2N)求log根号2（M/N)的值已知lgm*lgn=4,其中m>1,n>1,求m*n的最小值若2lg(M-2N)=lgM+lgN,求M/N的值