计算分治复杂度的方法──主定理
假设有递归关系式T(n)=aT(\frac nb)+f(n)，其中n是问题规模，a是递推子问题数量，\frac nb为每个子问题的规模，f(n)为递归以外做的工作，则有
若f(n)=\text{O}(n^{log_ba-\varepsilon}),\varepsilon>0,那么T(n)=\Theta(n^{log_ba})
若f(n)=\Theta(n^{log_ba}),那么T(n)=\Theta(n^{log_ba}logn)
若f(n)=\Omega(n^{log_ba+\varepsilon}),\varepsilon>0,且对于某个常数c<1和所有充分大的n有af\frac nb\le cf(n),那么T(n)=\Theta(f(n))
主定理的三种情况看上去非常复杂，但是没关系，虽然严格证明困难，但意会一下还是可以的。
第1条和第3条中的ε其实是为了严谨做出的修正，我们意会的话可以忽略他们。
这样3条定理的意思就可以理解为：
1.$如果分治外的操作不比$n^{log_ba}$多，那么总的复杂度为$Θ(n^{log_ba})
更进一步地，可以理解为如果分治外的操作比分治操作增速慢，那么就是分治操作占主要复杂度。
2.$如果分治外的操作数量级和$n^{log_ba}$相当，那么总复杂度为$Θ(n^{log_ba}logn)
这是最常见的情况，如果数量级相当，那么总复杂度还要再乘上logn。
如果分治外操作数量级不比n^{log_ba}小，那么当n很大时，总复杂度会趋向于Θ(f(n))
也就是说如果分治外的操作非常慢，那么算法就会被这些操作占主导，分治的作用减弱。
复杂度分析
以归并排序为例，首先分治的b和a都是2，也就是说问题规模每次减少一半，问题数量每次增加1倍。
那么我们分治外操作就要和Θ(n^{log_22})也就是和Θ(n)相比
显然，把两半序列合并成一个序列，n个元素中的每一个都要被访问到。
因此分治外操作的复杂度f(n)=Θ(n)。
所以根据主定理，归并排序的总复杂度就是Θ(nlogn)的
「那我要是三分归并排序，会不会让速度变得更快呀？」
答案是会更快，但是复杂度没有变。
更快的原因是三分会让层数降低，但是复杂度还是得靠主定理算。
a=3,b=3,f(n)=n
那么主定理告诉我们，T(n)=Θ(nlogn)
有同学会问，层数不是降为log_3n了吗，如何从分层的角度理解呢？
事实上，三分之后，复杂度为Θ(nlog_3n)=Θ(\frac{nlogn}{log_32})=Θ(nlogn)
这里用了换底公式，给log_3n换出一个\frac{1}{log_32}的常数。
而常数在复杂度分析里是不考虑的。