《算法导论（原书第3版)》 ──   Introduction to Algorithms, third edition

主定理

规模为n的问题通过分治，得到a个规模为n/b的问题，每次递归带来的额外计算为c(n^d)
T(n) <= aT(n/b)+c(n^d)
那么就可以得到问题的复杂度为：

• T(n) = O(n^d log(n)), if a = b^d
• T(n) = O(n^d ), if a < b^d
• T(n) = O(n^logb(a))), if a > b^d

证明方法

本来使用主定理是可以免去画递归树的，但为了证明主定理，还是需要画树。

可见，每次递归把问题分为a个规模为n/b的子问题。从根节点开始，共有logb(n)+1层，叶子节点数为a^(logb(n))。那么，第j层共有a^j个子问题，每个问题规模为n/b^j，每个子问题运算量为c*(n/b^j)^d需要完成的计算量为：

求和得到整个问题的运算量：

那么，根据a与b^d的关系，很容易得到主定理。