主定理证明（master theorem proof）

题目

主定理证明（master theorem proof）
T(1)=d and for n>1,T(n)=aT(n/b)+cn n is a
power of b;prove
􀁺 if ab,T(n)=O(nlogba)//b为底 logba 为n的次数
谁能帮我写出详细的证明 ,而且每一步说明原因；多谢!

答案

由问题有T(1)=dT(n)=aT(n/b)+cn,且有n=b^a 这个递推式描述了大小为n的原问题分成若干个大小为n/b的子问题,其中a个子问题需要求解,而cn是合并各个子问题的解需要的工作量.下面使用扩展递推技术对通用分治递推式进行推...