大 数 乘 法

输入两个很大的正整数，输出它们的乘积。比如

输入：1111111111111 1111111111111

输出：1234567901234320987654321

主定理内容

设\(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）与时间复杂度"