|
转自GoogleSite算法导论习题解答，先fork一下
算法导论其实已经给出了具体的证明步骤，但是还是有些省略，此文章是对主定理进行了完全的证明；
主定理的证明大致分为两个阶段：
(1)假设n为b的整数次幂，如1,b,b^2,b^3….
(2)不限定n的范围，n可以为任意整数；
首先我们先证明第一阶段，即n=b^i；
一、第一阶段
我们先画出递归树：
根据画出的递归树我们能够计算出T(n)：
第一种情况证明：
第二种情况证明： 
第三种情况证明： 
现在我们证明了当n为b的幂时的情况，下一阶段将要考虑n为任意整数的情况； 二、第二阶段 
我们只考虑第一种情况，第二种情况证明类似； 我们也将证明分为三类： 
我们先需要根据递归树写出T(n)的计算公式： 
第一种情况证明： 
第二种情况证明： 
第三种情况证明： 
就此证毕！ |
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/222733.html原文链接：https://javaforall.net
