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

01

主定理的证明大致分为两个阶段:
  1. 假设n为b的整数次幂,如1,b,b^2,b^3….
  2. 不限定n的范围,n可以为任意整数;
首先我们先证明第一阶段,即n=b^i;
 
 
一、第一阶段
 
 
我们先画出递归树:
 
02
 
根据画出的递归树我们能够计算出T(n):
 
03
第一种情况证明:
04
第二种情况证明:
 
05
第三种情况证明:
06
现在我们证明了当n为b的幂时的情况,下一阶段将要考虑n为任意整数的情况;
 
 
二、第二阶段
07
我们只考虑第一种情况,第二种情况证明类似;
 
我们也将证明分为三类:
08
我们先需要根据递归树写出T(n)的计算公式:
09
第一种情况证明:
10
第二种情况证明:
11
第三种情况证明:
12