# 分治

1. 先把原本的问题分为独立的子问题，分开来处理，再合并
   - 与动态规划的不同：分治子问题各异，没有重叠
   - 与贪心算法的不同：贪心中贪心的一步已经解决，无需再分

2. 大数相乘
   - 两个 $n$ 位的整数相乘，如果按照竖式方法，需要 $O(n^2)$ 次计算
   - $X=a\cdot 2^{n/2}+b$，$Y=c\cdot 2^{n/2}+d$，$XY=ac\cdot2^n+(ad+bc)\cdot2^{n/2}+bd$，但这实际上没有减少计算量，因为 $T(n)=4T(n/2)+O(n)$，依然为 $O(n^2)$，需要继续变换
   - $XY=ac\cdot2^n-((a-b)(c-d)-ac-bd)\cdot2^{n/2}+bd$ 或 $XY=ac\cdot2^n+((a+b)(c+d)-ac-bd)\cdot2^{n/2}+bd$ ，变为 $T(n)=3T(n/2)+O(n)$，此时为 $O(n^{\log_23})$

3. 矩阵相乘
   - $C=AB$，$C_{ij}=\sum_{k=1}^na_{ik}b_{kj}$，直接算需要 $O(n^3)$ 次运算
   - 如果对 $A$ 和 $B$ 进行四方切分，有 $$\left(\begin{matrix}A_1&A_2\\A_3&A_4\end{matrix}\right)\times\left(\begin{matrix}B_1&B_2\\B_3&B_4\end{matrix}\right)=\left(\begin{matrix}A_1B_1+A_2B_3&A_1B_2+A_2B_4\\A_3B_1+A_4B_3&A_3B_2+A_4A_4\end{matrix}\right)$$ 时间复杂度为 $T(n)=8T(n/2)+O(n^2)$，复杂度依然为 $O(n^3)$
   - 可以构造 $M_1=(A_1+A_4)(B_1+B_4),M_2=(A_3+A_4)B_1,M_3=A_1(B_2-B_4),M_4=A_4(B_3-B_1),M_5=(A_1+A_2)B_4,M_6=(A_3-A_1)(B_1+B_2),M_7=(A_2-A_4)(B_3+B_4)$，则有 $C_1=M_1+M_4-M_5+M_7,C_2=M_3+M_5,C_3=M_2+M_4,C_4=M_1-M_2+M_3+M_6$，时间复杂度为 $T(n)=7T(n/2)+O(n^2)$，复杂度为 $O(n^{\log_27})$
   - 如果按 $3\times3$ 或 $5\times5$ 分，则有可能更好，目前最好的可以达到 $n^{2.326}$ 左右

4. 坏棋盘问题
   - 一个 $2^k\times2^k$ 的棋盘，其中有一个方格被挖掉，现在要用 $L$ 型的骨牌覆盖整个棋盘
   - 取 $n=2^k$，则总共约要 $\Theta(n^2)=\Theta(4^k)$ 个骨牌
   - 将原本的棋盘划分为四个一样大小的棋盘，原本没有被挖掉方块的三块连着的地方填一个骨牌，这样就可以将问题分解为四个子问题，每个子问题的规模为 $n/2$，因此总的时间复杂度为 $T(k)=4T(k-1)+O(1)$，复杂度为 $O(4^k)$，也就是需要的骨牌数，因此不能更好了

5. 多项式乘法
   - 多项式 $A(x)=\sum_{j=0}^{n-1}a_jx^j$，$x$ 和 $a_j$ 均在域 $\mathbb{F}$ 中
   - 两个多项式相乘 $C(x)=A(x)B(x)$ 最直接的方法需要 $O(n^2)$ 次乘法
   - 多项式还可以用别的方法表示，系数表示法 $a=(a_0,a_1,\ldots,a_{n-1})$，点值表示法 $P=\{(x_0,y_0),(x_1,y_1),\ldots,(x_{n-1},y_{n-1})\}$，其中 $y_i=A(x_i)$ 且 $x_i$ 各异；对点值表示法，两多项式相乘时间复杂度为 $O(n)$
   - 给定 $x_0$ 和系数表达，求 $A(x_0)$ 时间复杂度为 $O(n)$，$A(x_0)=a_0+x_0(a_1+x_0(a_2+\cdots+x_0(a_{n-2}+x_0a_{n-1})))$
   - 给定一个点值表示法，要求系数，需要使用拉格朗日插值法，时间复杂度为 $O(n^2)$
   - 两个多项式相乘，可以先将两个多项式转换为点值表示法，然后相乘，再转换为系数表示法，时间复杂度为 $O(n\log n)$
   - 如何选取 $2n$ 个点？选取 $2n$ 次单位复数根
   - $n$ 次单位复数根有 $\omega_{dn}^{dk}=\omega_n^k$，$\omega_n^{n/2}=\omega_2=-1$，$(\omega_n^k)^2=\omega_{n/2}^k$，$\sum_{j=0}^{n-1}(\omega_n^k)^j=0$
   - 称 $y=(y_0,y_1,\ldots,y_{n-1})=DFT_n(a)$ 为 $a=(a_0,a_1,\ldots,a_{n-1})$ 的离散傅里叶变换，其中 $y_k=A(\omega_n^k)=\sum_{j=0}^{n-1}a_j\omega_n^{kj}$
   - 计算 $DFT_n(a)$ 只需 $O(n\log n)$，首先 $A(x)=A''(x^2)+xA'(x^2)$，其中 $A''(x)=a_0+a_2x+\cdots+a_{n-2}x^{n/2-1},A'(x)=a_1+a_3x+\cdots+a_{n-1}x^{n/2-1}$，而且每个子问题因为 $(\omega_n^k)^2=\omega_{n/2}^k$，规模减小一半，因此时间复杂度为 $T(n)=2T(n/2)+O(n)$，为 $O(n\log n)$ 