# Overview

分治本身没什么能多说的

构建分治的核心在于怎么 merge；

配合主定理 or 递归树，即可求解时间复杂度

# 多项式乘法（FFT）

视频教程

利用插值思想，我们在计算多项式乘法时，新奇的选择把$<a_0,a_1,\dots,a_{n-1}>$evaluate 为$n+1$ 维点

之后经过叹为观止的操作，红框变为$O(nlogn)$，红黄框变为$O(n)$，红框变为$O(nlogn)$

红框是分支算法的体现处，其核心在于把原多项式分解为：

$$P(x)=xP_{odd}(x^2)+P_{even}(x^2)$$

$P(x)$ 函数被我们定义为：对于$n-1$ 次多项式$a(x)$

• 输入为$<a_0,a_1,\dots,a_{n-1}>$ 和向量$x$，$x$ 长度为$k$
• 计算其多项式结果$y$，$y$ 长度为$k$

若对称取点，那么对于$k/2$ 个点：

$$\begin{align*} &\begin{bmatrix} y_1\\y_2\\\vdots\\y_{k/2} \end{bmatrix} =\!\!\!\!\!\!& \begin{bmatrix} y_{odd1}\\y_{odd2}\\\vdots\\y_{oddk/2} \end{bmatrix} \circ\; & \begin{bmatrix} x_{1}\\x_{2}\\\vdots\\x_{k/2} \end{bmatrix} \!\!\!\!\!&+ \begin{bmatrix} y_{even1}\\y_{even2}\\\vdots\\y_{evenk/2} \end{bmatrix} \\ \\ &\begin{bmatrix} y_1'\\y_2'\\\vdots\\y_{k/2}’ \end{bmatrix} =\!\!\!\!\!\!& \begin{bmatrix} y_{odd1}\\y_{odd2}\\\vdots\\y_{oddk/2} \end{bmatrix} \circ\; & \begin{bmatrix} -x_{1}\\-x_{2}\\\vdots\\-x_{k/2} \end{bmatrix} \!\!\!\!\!&+ \begin{bmatrix} y_{even1}\\y_{even2}\\\vdots\\y_{evenk/2} \end{bmatrix} \end{align*}$$

有了$y_{odd}$，$y_{even}$ 两个向量，那剩下的工作就是：

• $y_{odd}$ 与向量$x$（或$-x$）的一半对应位置相乘，$O(k)$
• 相加，$O(k)$

计算量削减的核心：选定的点是$[\pm x_1,\dots,\pm x_n]$，平方后需要计算的向量维度减半。比如一开始要算 32 个点$[\pm x_1,\dots,\pm x_{16}]$ 的多项式结果$y$，平方后只要算 $[x_1^2,\dots,x_{16}^2]$ 16 个点的多项式结果

当$k$ 是$n$ 的一次函数（$k=n\;or\;k=2n-1$），那么$P(x)$ 函数的时间复杂度：

$$T(n)=2T(n/2)+O(n)$$

根据主定理，$T(n)=O(nlogn)$；

分治的出口为$n=1$，此时多项式为常数函数
无论是 evaluate 多项式$a(n)$，$n-1$ 维多项式找$n$ 个点
还是 evaluate 多项式相乘结果$a(n)b(n)$，$2n-2$ 维多项式找$2n-1$ 个点
此时找一个点即可