主页‎ > ‎Chapter 04(C)‎ > ‎

主定理证明

算法导论其实已经给出了具体的证明步骤,但是还是有些省略,此文章是对主定理进行了完全的证明;


主定理的证明大致分为两个阶段:

(1)假设n为b的整数次幂,如1,b,b^2,b^3....
(2)不限定n的范围,n可以为任意整数;

首先我们先证明第一阶段,即n=b^i;


一、第一阶段


我们先画出递归树:


根据画出的递归树我们能够计算出T(n):



第一种情况证明:




第二种情况证明:




第三种情况证明:



现在我们证明了当n为b的幂时的情况,下一阶段将要考虑n为任意整数的情况;


二、第二阶段




我们只考虑第一种情况,第二种情况证明类似;

我们也将证明分为三类:



我们先需要根据递归树写出T(n)的计算公式:





第一种情况证明:




第二种情况证明:





第三种情况证明:




就此证毕!













Comments