主定理最早出现在《算法导论》中，提供了分治方法带来的递归表达式的渐近复杂度分析。
规模为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=1，b=2，c=0
-
复杂度为n^0 O(log n)
二叉树遍历
每次问题规模减半，a=2，b=2，c=0
复杂度为n O(n)
快速排序
-
随机选择待排序序列中的一个数字作为划分字问题的标准，划分是否平均影响算法复杂度
-
每次问题规模减半，a=2，b=2，c=1
-
复杂度为n^2 O(n log n)
-
最差情况下，复杂度为O(n^2)
归并排序
-
数据列均分为两部分，分别排序，之后以O(n)的复杂度进行合并，空间复杂度O(n)
-
每次问题规模减半，a=2，b=2，c=1
-
复杂度为n log(n)