Posted on 2008-03-30 22:26
迎风十八刀 阅读(167)
评论(0) 编辑 收藏 所属分类:
算法
求解T(n)=T(ceil(n/2))+1
猜测解为O(lgn)
只需证T(n)<=clg(n-b)。于是T(n)<=clg(ceil(n/2-b))+1
<=clg(n/2-b+1)+1
...
<=clg(n-b)
主方法:
形如T(n)=aT(n/b)+f(n),注意a>=1,b>1
比较f(n)和nlogba，则T(n)为较大者，如果f(n)=Q(nlogba),则T(n)=Q(nlogbalgn)