主定理与时间复杂度
主要解决：根据时间复杂度的递推关系，求时间复杂度
主定理内容
设\(a \geq 1\)和\(b > 1\)为常数，设f(n)为一函数，T(n)有递推式 \[ T(n)=aT(\frac n b)+f(n) \] 其中\(\frac nb\) 指\(\left\lfloor\dfrac{n}{b} \right\rfloor\)和\(\left\lceil\dfrac{b}{n} \right\rceil\)，可以证明，略去上下取整不会对结果造成影响。那么\(T(n)\)可能有如下的渐进界
（1）若\(f(n) < n^{\log_ba}\)，且是多项式的小于。即 \[ \exists \epsilon>0,有f(n)=\mathcal{O}(n^{\log_ba-\epsilon}),则T(n)=\mathcal{O}(n^{\log_ba}) \] （2）若\(f(n) = n^{\log_ba}\)，则\[T(n)=\mathcal{O}(n^{\log_ba}\log n)\]
（3）若\(f(n) > n^{\log_ba}\)，且是多项式的大于。即 \[ \exists \epsilon>0,有f(n)=\mathcal{O}(n^{\log_ba-\epsilon}),则T(n)=\mathcal{O}(n^{\log_ba}) \\ 且对\exists c<1与所有足够大的n,有af(\frac nb)\leq cf(n),则T(n)=\mathcal{O}(f(n)) \]
主定理证明
可以画递归树
可见，每次递归把问题分为\(a\)个规模为\(\frac nb\)的子问题。从根节点开始，共有\(\log_bn+1\)层，叶子节点数为\(a^{\log_bn}\)。那么，第j层共有\(a^j\)个子问题，每个问题规模为\(n/b^j\)，每个子问题运算量为\(c*(\frac n{b^j})^d\)，每一层需要完成的计算量为
\[ a^jf(\frac n{b^j}) \] 求和得到整个问题的运算量，d为f(n)的阶数 \[ \sum_{j=0}^{\log_bn} a^jf(\frac n{b^j}) = Cn^d\sum_{j=0}^{\log_bn}(\frac a{b^d})^j \] 分类讨论
（1）若\(f(n) < n^{\log_ba}\)，且是多项式的小于，即\(d<\log_ba\)
不会了
（2）若\(f(n) = n^{\log_ba}\), 即 \[ Cn^d\sum_{j=0}^{\log_bn}(\frac a{b^d})^j = Cn^d\log_b n = \mathcal{O}(n^{\log_ba}\log n) \] （3）若\(f(n) > n^{\log_ba}\)，且是多项式的大于。即
不会了
主定理应用
二分搜索
- 每次问题规模减半，a=1，b=2，d=0
- 复杂度为n^0 log(n) = log(n)。
快速排序
- 随机选择待排序序列中的一个数字作为划分字问题的标准，划分是否平均影响算法复杂度
- 每次问题规模减半，a=2，b=2，d=1
- 复杂度为n^2 log(n)
- 最差情况下，复杂度为O(n^2)
归并排序
- 数据列均分为两部分，分别排序，之后以O(n)的复杂度进行合并，空间复杂度O(n)
- 每次问题规模减半，a=2，b=2，d=1
- 复杂度为n log(n)
基数排序(Radix sort)
- 对于待排序的整数序列，从最低位到最高位每次按照相应的位排序一次
- 每次递归问题规模变为原来的1/10，但需要求解10个子问题，额外运算为O(n)的，a=10，b=10，d=1
- 复杂度为n^1 log(n) = n log(n)，近似为O(kN)，k为整数的位数
快速傅里叶变换：FFT
- 每次问题规模减半，a=2，b=2，d=1
- 复杂度为n log(n)
Karatsuba快速乘法
- 正常两个n位数乘法为n^2
- 算法把两个乘数各分为高低位两部分，如XY = (a+b) (c+d) = ac+bd + (bc+ad) = ac+bd+(ac+bd - (a-b)(c-d))
- 只需要ac,bd,(a-b)(c-d)三次乘法
- 每次问题规模减半，但需要解3个子问题，加法是O(n)的，a=3，b=2，d=1
- 复杂度为n^log2(3)
参考文献
[1] https://blog.csdn.net/caozhk/article/details/24734371 "主定理的证明及应用举例" [2] https://blog.csdn.net/lanchunhui/article/details/52451362 "主定理（Master Theorem）与时间复杂度"