主定理证明(master theorem proof)
来源:学生作业帮 编辑:搜狗做题网作业帮 分类:数学作业 时间:2024/08/18 01:08:43
主定理证明(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)=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的次数
谁能帮我写出详细的证明 ,而且每一步说明原因;多谢!
![主定理证明(master theorem proof)](/uploads/image/z/4726775-47-5.jpg?t=%E4%B8%BB%E5%AE%9A%E7%90%86%E8%AF%81%E6%98%8E%EF%BC%88master+theorem+proof%EF%BC%89)
由问题有
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]
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]
主定理证明(master theorem proof)
微积分定理 THEOREM
the weierstrass theorem (维尔斯特拉斯定理
各态历经定理(ergodic theorem)指的内容是什么呢?
求二项式定理,英文是Binomial Theorem
关於Pythagoras Theorem(毕氏定理/商高定理)
定律(LAW)与定理(THEOREM)有什么区别?
算法的一些习题,一 完成下列关于复杂度的问题(1)使用定义证明:证明2n=o(n2) (2)使用master定理求解T(
proof
OLS estimator proof.统计学,经济计量学,证明.
Earnshaw's theorem 谁知道这是什么定理?最好具体内容也有~
切割线定理证明(不用弦切角定理)我还没学