算法复杂度中的主定理（master theorem）

导言

什么是主定理，引用维基百科的介绍，在算法分析中，主定理（英语：master theorem）提供了用渐近符号（大O符号）表示许多由分治法得到的递推关系式的方法。所以，在算法复杂度分析时，我们经常需要使用主定理做复杂度的推导，尤其是各种类型的分治算法，比如二分搜索、归并排序、二叉树的遍历等算法。

理论

算法存在递推关系式

证明

总结

以上的证明手写输出，在电脑上面打公式太麻烦，另外证明过程采用的比较简单直接的方式，没有使用特别严格的数学证明方法，便于理解，简单来说，如果a<b^d，那么T(n)主要看O(n^d)这项，如果a==b^d，那么T(n)需要看展开的每一项，如果a>b^d，那么最主要的是看展开后的最后一层子问题，后面有时间，会补充一篇根据主定理推导算法复杂度的文章。