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

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

代换法解递归式证明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

0