Posted on 2008-03-30 22:26
迎風十八刀 閱讀(172)
評論(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)