【复杂度相关】主定理

**计算分治复杂度的方法──主定理** 假设有递归关系式$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}$的常数。 而常数在复杂度分析里是不考虑的。