由问题有
T(1)=d
T(n)=aT(n/b)+cn,且有n=b^a
这个递推式描述了大小为n的原问题分成若干个大小为n/b的子问题,其中a个子问题需要求解,而cn是合并各个子问题的解需要的工作量.下面使用扩展递推技术对通用分治递推式进行推导
T(n)=aT(n/b)+cn
=a(aT(n/b^2)+c*n/b)+cn
…………………………
=a^aT(n/b^a)+a^(a-1)*c*n/b^(a-1)+...+a*c*n/b+cn
=c∑(i从0到a)[a^(a-i)]*n/b^(a-i)(因为n=b^a)
=c∑(i从0到a)[a^(a-i)]*b^i
=c*a^a∑(i从0到a)[(b/a)^i]
这个求和是个几何级数,其值依赖与比率b/a,注意到a^a=a^(logbn)=n^(logba),则有下3种情况：
(1)a>b:∑(i从0到a)[(b/a)^i]