主定理 Master theorem

函数渐进增长率的表示（$O、\Omega、\Theta$O、Ω、Θ）

（不做详细介绍，仅为个人理解）
$f(n) = O(g(n))$f(n)=O(g(n)) 表示 $g(n)$g(n) 为$f(n)$f(n) 的渐进上界
$f(n) = \Omega(g(n))$f(n)=Ω(g(n)) 表示 $g(n)$g(n) 为$f(n)$f(n) 的渐进下界
$f(n) = \Theta(g(n))$f(n)=Θ(g(n)) 表示 $g(n)$g(n) 为 $f(n)$f(n) 的紧确界（有着相同的渐进增长率）

主定理与分治法

先回忆一下分治法：
将一个规模为 $n$n 的问题，分成几个规模为 $\dfrac{n}{b}$bn​ 的子问题，然后将这几个子问题的结果进行整合等一系列处理，假设这一过程所需要花费的时间函数为 $f(n)$f(n) ， 所以整个分治算法需要消耗的时间函数
$T(n) = aT(\lceil \dfrac {n}{b}\rceil) + f(n)$T(n)=aT(⌈bn​⌉)+f(n)

当我们关注渐进增长率的时候，可以忽略 $T(n)$T(n) 中的向上取整函数，所以上述式子就变成了$T(n) = aT(\dfrac {n}{b}) + f(n)$T(n)=aT(bn​)+f(n)

而主定理刚好可以解决这种函数形式的渐进增长率的问题。

主定理：

对于 $T(n) = aT(\dfrac {n}{b}) + f(n)$T(n)=aT(bn​)+f(n)

（a）如果存在正数 $\varepsilon >0$ε>0 使得 $f(n) = O(n^{\log _{b}a-\varepsilon })$f(n)=O(nlogb​a−ε) , 那么 $T(n)\in \Theta(n^{\log _{b}a})$T(n)∈Θ(nlogb​a)
（b）如果 $f(n) = \Theta(n^{\log _{b}a })$f(n)=Θ(nlogb​a), 那么 $T(n)\in \Theta(n^{\log _{b}{a}}\log_2n)$T(n)∈Θ(nlogb​alog2​n)
（c）如果存在正数 $\varepsilon >0$ε>0 使得 $f(n) = \Omega(n^{\log _{b}a+\varepsilon })$f(n)=Ω(nlogb​a+ε) , 并且存在 $n_0$n0​ 及 $c<1$c<1 使得对于所有$n>n_0$n>n0​ 都有$af(\dfrac {n}{b})\leq cf(n)$af(bn​)≤cf(n)

那么 $T(n)\in \Theta(f(n))$T(n)∈Θ(f(n))

由此可见，有很多形式的 $f(n)$f(n) 是不满足主定理的应用条件的。比如
$T(n) = 2T(n/2) + nlog(n)$T(n)=2T(n/2)+nlog(n)

但是如果利用主定理的证明方法（对 $T(n/2)$T(n/2) 进行展开）我们可以得到
$T(n)\in \Theta (n(logn)^2)$T(n)∈Θ(n(logn)2)

所以，老师您不觉得这个主定理的条件太苛刻了吗？市面上的主定理不香吗？？？

大数乘法

Karatsuba 算法

回顾一下上周利用 Karatsuba algorithm求解大数乘法的过程：
将$A，B$A，B 拆分成 2 部分 ：
$A = A_12^{n/2} + A_0$A=A1​2n/2+A0​

$B = B_12^{n/2} + B_0$B=B1​2n/2+B0​

那么
$AB = A_1B_1·2^n + (A_1B_0 + B_1A_0)2^{n/2} + A_0B_0$AB=A1​B1​⋅2n+(A1​B0​+B1​A0​)2n/2+A0​B0​

$= A_1B_1·2^n + ((A_1+A_0)(B_1+B_0) - A_1B_1 - A_0B_0)2^{n/2} + A_0B_0$=A1​B1​⋅2n+((A1​+A0​)(B1​+B0​)−A1​B1​−A0​B0​)2n/2+A0​B0​

可见，Karatsuba 算法的关键在于减少了计算过程中大数乘法的次数。
该算法时间复杂度：
$T(n)\in O(n^{1.58}) << n^2$T(n)∈O(n1.58)<<n2

Karatsuba 算法的泛化

接下来我们来泛化这个过程，首先尝试把$A，B$A，B 拆分成 3 部分 ：

$A = A_22^{2k}+A_12^{k} + A_0$A=A2​22k+A1​2k+A0​

$B = B_22^{2k} +B_12^{k} + B_0$B=B2​22k+B1​2k+B0​

$AB = C_4·2^{4k} + C_32^{3k} + C_22^{2k}+C_12^k+C_0$AB=C4​⋅24k+C3​23k+C2​22k+C1​2k+C0​

其中

$C_4=A_2B_2$C4​=A2​B2​
$C_3=A_1B_2+A_2B_1$C3​=A1​B2​+A2​B1​
$C_2=A_0B_2+A_1B_1+A_2B_0$C2​=A0​B2​+A1​B1​+A2​B0​
$C_1=A_0B_1+A_1B_0$C1​=A0​B1​+A1​B0​
$C_0=A_0B_0$C0​=A0​B0​

想用5个乘法来获取这五个系数不是一件容易的事情，所以我们可以采取别的办法。
引入多项式
$P_A(x) = A_2x^2 + A_1x + A_0$PA​(x)=A2​x2+A1​x+A0​

$P_B(x) = B_2x^2 + B_1x + B_0$PB​(x)=B2​x2+B1​x+B0​

那么

$A = P_A(2^k) = A_2(2^k)^2 + A_1(2^k) + A_0$A=PA​(2k)=A2​(2k)2+A1​(2k)+A0​

$B = P_B(2^k) = B_2(2^k)^2 + B_1(2^k) + B_0$B=PB​(2k)=B2​(2k)2+B1​(2k)+B0​
$AB =P_A(2^k)P_B(2^k) =C_4·2^{4k} + C_32^{3k} + C_22^{2k}+C_12^k+C_0$AB=PA​(2k)PB​(2k)=C4​⋅24k+C3​23k+C2​22k+C1​2k+C0​
$AB$AB 相乘的结果中5个系数的值分别与 $P_A(2^k)P_B(2^k)$PA​(2k)PB​(2k) 结果中 5 个系数对应相等。那么令
$P_C(x) = P_A(x)P_B(x) = C_4·{x^4} + C_3{x^3} + C_2{x^2}+C_1x+C_0$PC​(x)=PA​(x)PB​(x)=C4​⋅x4+C3​x3+C2​x2+C1​x+C0​
我们就可以把 $A、B$A、B 这 2 个数的乘积问题转化为当 $x = 2^k$x=2k 时多项式 $P_C$PC​ 的值，在二进制中，最终的结果可以由五个系数的值移位相加获得，所以求解的关键就在于如何获取这 5 个系数。

对于一个一元四次方程而言，我们需要代入5个值就可以得出相应的系数。
于是我们代入 5 个最简单的 $x$x 的值：
$-2,-1,0,1,2$−2,−1,0,1,2

那么
$P_C(-2)= P_B(-2) P_A(-2)\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = (A_0 - 2A_1 + 4A_2)(B_0 - 2B_1 + 4B_2)$PC​(−2)=PB​(−2)PA​(−2)              =(A0​−2A1​+4A2​)(B0​−2B1​+4B2​)

$P_C(-1)= P_B(-1) P_A(-1)\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = (A_0 - A_1 + A_2)(B_0 - B_1 + B_2)$PC​(−1)=PB​(−1)PA​(−1)              =(A0​−A1​+A2​)(B0​−B1​+B2​)

$P_C(0)= P_B(0) P_A(0)\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = A_0 B_0$PC​(0)=PB​(0)PA​(0)              =A0​B0​

$P_C(1)= P_B(1) P_A(1)\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = (A_0 + A_1 + A_2)(B_0 + B_1 + B_2)$PC​(1)=PB​(1)PA​(1)              =(A0​+A1​+A2​)(B0​+B1​+B2​)

$P_C(2)= P_B(2) P_A(2)\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = (A_0 +2A_1 + 4A_2)(B_0 + 2B_1 + 4B_2)$PC​(2)=PB​(2)PA​(2)              =(A0​+2A1​+4A2​)(B0​+2B1​+4B2​)

（上述运算中，对于$P_A(x)$PA​(x) 和 $P_B(x)$PB​(x) 的运算只包含大数加法，所以所需的时间为$O(n)$O(n) 。而求解相应的 $P_C$PC​ 的值，只需要进行一次大数乘法。所以计算上述5个值一共需要 5 次大数乘法。）

现在，我们获取了 $P_C(-2),P_C(-1),P_C(0),P_C(1),P_C(2)$PC​(−2),PC​(−1),PC​(0),PC​(1),PC​(2) 的值，而根据多项式$P_C$PC​ 的定义，我们可以得到

$P_C(-2)= 16C_4- 8C_3+4C_2-2C_1+ C_0$PC​(−2)=16C4​−8C3​+4C2​−2C1​+C0​
$P_C(-1)= C_4 - C_3 + C_2 - C_1+C_0$PC​(−1)=C4​−C3​+C2​−C1​+C0​
$P_C(0)= C_0$PC​(0)=C0​
$P_C(1)= C_4 +C_3 + C_2 + C_1+C_0$PC​(1)=C4​+C3​+C2​+C1​+C0​
$P_C(2)= 16C_4 + 8C_3+4C_2+2C_1+ C_0$PC​(2)=16C4​+8C3​+4C2​+2C1​+C0​

所以我们得到了一个五元一次方程，接下来只需要对线性方程进行求解就可以了。相应地：

$C_0 = P_C(0)$C0​=PC​(0)

$C_1 = \dfrac{P_C(-2)}{12} - \dfrac{2P_C(-1)}{3} + \dfrac{2P_C(1)}{3} -\dfrac{P_C(-2)}{12}$C1​=12PC​(−2)​−32PC​(−1)​+32PC​(1)​−12PC​(−2)​

$C_2 =- \dfrac{P_C(-2)}{24} + \dfrac{2P_C(-1)}{3} - \dfrac{5P_C(1)}{4} -\dfrac{P_C(-2)}{12}$C2​=−24PC​(−2)​+32PC​(−1)​−45PC​(1)​−12PC​(−2)​

$C_3 = -\dfrac{P_C(-2)}{12} + \dfrac{P_C(-1)}{6} - \dfrac{P_C(1)}{6} +\dfrac{P_C(-2)}{12}$C3​=−12PC​(−2)​+6PC​(−1)​−6PC​(1)​+12PC​(−2)​

$C_4 = \dfrac{P_C(-2)}{24} - \dfrac{P_C(-1)}{6} + \dfrac{P_C(0)}{4} - \dfrac{P_C(1)}{6} +\dfrac{P_C(-2)}{24}$C4​=24PC​(−2)​−6PC​(−1)​+4PC​(0)​−6PC​(1)​+24PC​(−2)​

最终，我们可以得到

$AB =P_A(2^k)P_B(2^k) =C_4·2^{4k} + C_32^{3k} + C_22^{2k}+C_12^k+C_0$AB=PA​(2k)PB​(2k)=C4​⋅24k+C3​23k+C2​22k+C1​2k+C0​
回顾上述过程，完整算法如下：

Step 1: 将$A,B$A,B 拆分成3部分
$A = A_22^{2k}+A_12^{k} + A_0$A=A2​22k+A1​2k+A0​

$B = B_22^{2k} +B_12^{k} + B_0$B=B2​22k+B1​2k+B0​

Step 2: 建立多项式
$P_A(x) = A_2x^2 + A_1x + A_0$PA​(x)=A2​x2+A1​x+A0​

$P_B(x) = B_2x^2 + B_1x + B_0$PB​(x)=B2​x2+B1​x+B0​

$P_C(x) = P_A(x)P_B(x) \\\ \ \ \ \ \ \ \ \ \ \ \ = C_4·{x^4} + C_3{x^3} + C_2{x^2}+C_1x+C_0$PC​(x)=PA​(x)PB​(x)            =C4​⋅x4+C3​x3+C2​x2+C1​x+C0​
则
$AB =P_A(2^k)P_B(2^k)$AB=PA​(2k)PB​(2k)
Step 3: 代入 5 个 不同的 $x$x ， 得到$P_C(-2),P_C(-1),P_C(0),P_C(1),P_C(2)$PC​(−2),PC​(−1),PC​(0),PC​(1),PC​(2) 的值。（需要5次大数乘法）

Step 4: 建立关于 $C_4、 C_3、C_2、C_1、C_0$C4​、C3​、C2​、C1​、C0​ 的线性方程组，通过线性方程组求解这五个系数的值。

Step 5: $AB =C_4·2^{4k} + C_32^{3k} + C_22^{2k}+C_12^k+C_0$AB=C4​⋅24k+C3​23k+C2​22k+C1​2k+C0​
算法时间复杂度：
上述过程仅需5次大数乘法以及多次大数加法，故该算法的时间复杂度为
$T(n) = 5T(\dfrac{n}{3}) + O(n)$T(n)=5T(3n​)+O(n)

$T(n) = O(n^{\log _{3}5 }) < O(n^{1.47})$T(n)=O(nlog3​5)<O(n1.47)

而 Karatsuba 的方法时间复杂度为 $O(n^{\log _{2}3})\approx O(n^{1.58}) > O(n^{1.47})$O(nlog2​3)≈O(n1.58)>O(n1.47)，可见，如果我们把 $A、B$A、B 分成3部分，算法复杂度会有所下降。

那如果把 $A、B$A、B 分成 4 部分 甚至5个部分呢？上述结果是否意味着随着"部分" 个数的增加，求解大数乘法的复杂度会一直下降呢？

泛化该方法的过程如下：
Step 1: 将 $A、B$A、B 分成 $p+1$p+1 个部分，每个部分有 $k$k 位

则

$A = A_p2^{kp}+A_{p-1}2^{k(p-1)} +...+ A_0$A=Ap​2kp+Ap−1​2k(p−1)+...+A0​

$B = B_p2^{kp}+B_{p-1}2^{k(p-1)} +...+ B_0$B=Bp​2kp+Bp−1​2k(p−1)+...+B0​

Step 2: 建立对应的多项式
$P_A(x) = A_px^{p}+A_{p-1}x^{p-1} +...+ A_0$PA​(x)=Ap​xp+Ap−1​xp−1+...+A0​

$P_B(x) = B_px^{p}+B_{p-1}x^{p-1} +...+ B_0$PB​(x)=Bp​xp+Bp−1​xp−1+...+B0​

$AB =P_A(2^k)P_B(2^k)$AB=PA​(2k)PB​(2k)

$P_C(x) = P_A(x)P_B(x) \\\ \ \ \ \ \ \ \ \ \ \ \ = C_{2p}·{x^{2p}} + C_{2p-1}{x^{2p-1}} +... +C_0$PC​(x)=PA​(x)PB​(x)            =C2p​⋅x2p+C2p−1​x2p−1+...+C0​

Step 3: 代入 $2p+1$2p+1 个 不同的 $x$x ， 得到相应的$P_A 、P_B$PA​、PB​，对应项相乘获得
$P_C(p),P_C(p-1),...,P_C(0),...P_C(-p+1),P_C(-p)$PC​(p),PC​(p−1),...,PC​(0),...PC​(−p+1),PC​(−p) （需要 $2p+1$2p+1 次大数乘法，即 $2p+1$2p+1 个 $P_A 、P_B$PA​、PB​ 相乘 ）

Step 4: 建立关于系数 $C$C 的线性方程组，通过线性方程组求解这 $2p+1$2p+1 个系数的值。

Step 5: $AB =C_{2p}·{x^{2p}} + C_{2p-1}{x^{2p-1}} +... +C_0$AB=C2p​⋅x2p+C2p−1​x2p−1+...+C0​
所以该算法的时间复杂度为
$T(n) = (2p+1)T(\dfrac{n}{p+1}) + O(n)$T(n)=(2p+1)T(p+1n​)+O(n)

$T(n) = \Theta(n^{\log_{p+1}{(2p+1)}})$T(n)=Θ(nlogp+1​(2p+1))

接下来我们把对数这部分进行化简

$n^{\log_{p+1}{(2p+1)}} < n^{\log_{p+1}{2(p+1)}} \\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =n^{(\log_{p+1}{2})+(\log_{p+1}({p+1}))} \\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =n^{1+\log_{p+1}{2}}\\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =n^{1+\dfrac{1}{\log_{2}{(p+1)}}}$nlogp+1​(2p+1)<nlogp+1​2(p+1)                     =n(logp+1​2)+(logp+1​(p+1))                     =n1+logp+1​2                     =n1+log2​(p+1)1​

这意味着如果 $p$p 足够大, 我们就可以把该算法的复杂度无线接近于线性。然而事实上，如果我们想让该算法的复杂度为 $O(n^{1.1})$O(n1.1) ，那么就会得到 $p+1 = 2^{10}$p+1=210 。也就是说我们需要把这2个大数分成 1024 个部分。

不仅如此，我们在求解 $2p+1$2p+1 个系数的时候，需要对 $P_A(p)、P_B(p)$PA​(p)、PB​(p) 进行赋值， 而$P_A(p) =A_pp^p +...+A_0$PA​(p)=Ap​pp+...+A0​ 这里面就涉及到了 $p^p$pp 和 $A_p$Ap​ 的乘法运算。由此可见，虽然理论上我们对 $P_A(x)、P_B(x)$PA​(x)、PB​(x) 进行赋值所需要的时间为 $T(n) = cn$T(n)=cn， 但实际上这个常数 $c$c 非常大。

归根到底，上述结果本质上是因为 $O$O 省去了函数的常数项系数，而在实际应用过程中，如果这个常数项系数超过了合理范围内，这种用 $O$O 的渐进估计将变得没有意义。

那么，既然我们不能通过将 $A,B$A,B 进行无限分割来降低求解大数乘法的复杂度，该算法的改进方向就变成了如何减化 $x_i^p$xip​ 。一种有效的方式就是利用复平面的单位圆，采用快速傅立叶变换 $(FFT)$(FFT)。具体方法我们将在下周进行介绍。

卷积

通过上述对大数乘法的分析，我们知道该算法的核心思想是通过建立多项式 $P_C(x) = P_A(x)P_B(x)$PC​(x)=PA​(x)PB​(x) 来获取相应系数的值。而这其中就包含了卷积的概念。

对于两个序列 $\overrightarrow {A} = (A_0,A_1,...,A_{p-1},A_p)$A=(A0​,A1​,...,Ap−1​,Ap​) 、 $\overrightarrow {B} = (B_0,B_1,...,B_{m-1},B_m)$B=(B0​,B1​,...,Bm−1​,Bm​) 以及对应的 2 个多项式

$P_A(x) = A_px^p + A_{p-1}x^{p-1}+...+A_1x+A_0$PA​(x)=Ap​xp+Ap−1​xp−1+...+A1​x+A0​

$P_B(x) = B_mx^m + B_{m-1}x^{m-1}+...+B_1x+B_0$PB​(x)=Bm​xm+Bm−1​xm−1+...+B1​x+B0​

如果我们对这两个多项式进行乘法运算，得到

$P_A(x)·P_B(x) =\sum ^{p+m}_{j=0} C_jx^j$PA​(x)⋅PB​(x)=j=0∑p+m​Cj​xj

其中

$C_j=\sum _{i+k=j}A_iB_k,\ \ \ \ \ \ 0\leq j \leq p+m$Cj​=i+k=j∑​Ai​Bk​,      0≤j≤p+m

那么 $C_j$Cj​ 所对应的序列 $\overrightarrow {C} = (C_0,C_1,...,C_{p+m-1},C_{p+m})$C=(C0​,C1​,...,Cp+m−1​,Cp+m​) 就是序列$\overrightarrow {A}、\overrightarrow {B}$A、B 线性卷积的结果。记为
$\overrightarrow {C}=\overrightarrow {A}* \overrightarrow {B}$C=A∗B

而我们上述讨论的算法也可以说是求解两个序列线性卷积的方法。

思考题（5个海盗分金条）

问题描述：
五个海盗分赃100根金条，他们将按照年龄顺序，每次由一个人对金条进行分配，然后所有人（包括分配者）对本次分配进行投票，如果赞成票少于等于总人数的一半，那么这个分配的人就会被杀死（太残暴了Omg。。）
假设这五个海盗都具备以下特质：
首要先保命
命保住了之后能拿多少钱就拿多少钱
在能拿同样钱的情况下，希望其他海盗能挂就挂
每个海盗都知道自己的顺序
所有人都很聪明且鸡贼，会做出当前情况下对自己最有利的选择。
那么如果你是第一个分配金条的人，你会怎么分配这100根金条呢？

个人见解（仅供参考）：
如果只剩下2个人： 不管怎么分配，分配的人都会被杀死，因为如果只有最后一个人他就会拿走所有金条，只要最后一个人投了反对票，分配的人就没了。
如果只剩下3个人：那么分配结果为100:0:0， 倒数第二个人肯定会投赞成票，因为如果反对的话他肯定就没命了。
如果只剩下4个人：98:0:1:1 这样最后2个人也会投赞成票，不然只剩下3个人的话他两就什么都分不到了。
如果一共有5个人：97:0:1:2:0 或者 97:0:1:0:2 这样除了分配者之外，为了使自己分到的更多，拿到金条的人都会投赞成票。