（n 次）单位根

• 一个单位的 $n$ 次根是 $w$，$w^n=1$
• 其中一个解是 1，但是引入复数，就会有其它解。方程的所有解都位于复平面，记 $w_n=e^{\frac{2 \pi i}{n}}$，则所有解为 $w_n^0, w_n^1,...,w_n^{n-1}$
• $w_n^n=1$
• $w_n^{k+n/2}=-w_n^k$
• $(w_n^k)^2=w_n^{2k}=w^k_{n/2}$

离散傅里叶变换

• 给定度为 n 的多项式

  $$ A=a_0+a_1x+a_2x^2+...+a_{n-1}x^{n-1} $$

  DFT 计算 $A(w_n^0), A(w_n^1), ..., A(w_n^{n-1})$

• 因为 $A=a_0+x(a_1+x(a_2+...)...)$，所以 $A(x)$ 可在 O(n) 时间计算出，所以 DFT 可在 O(n^2) 计算出

快速傅里叶变换

• 利用分治算法，可以在 O(nlogn) 时间算出 DFT

• 设

  $$ A^{[0]}=a_0 + a_2x^1+a_4x^2+...+a_{n-2}x^{\frac{n}{2}-1}\\ A^{[1]}=a_1 + a_3x^1+a_4x^2+...+a_{n-1}x^{\frac{n}{2}-1} $$

• 有 $A(x)=A^{[0]}(x^2)+xA^{[1]}(x^2)$
• 通过计算 $A^{[0]}, A^{[1]}$ 在 $(w_n^0)^2, (w_n^2)^2, ..., (w_n^{n-1})^2$ 处的单位根，可以算出 $A(w_n^0), A(w_n^1), ...,A(w_n^{n-1})$

• 因为 $(w_n^{k+n/2})^2=w_n^{2k+n}=w_n^{2k}$

  所以 $\{(w_n^0)^2,(w_n^1)^2,...,(w_n^{n-1})^2\}=\{(w_n^0)^2,(w_n^1)^2,...,(w_n^{n/2-1})^2\}$

  只需要计算 $A^{[0]}, A^{[1]}$ 在 n/2 个点而不是 n 个点处的值

• 因为 $(w_n^k)^2=w_n^{2k}=w_{n/2}^k$

  所以 $\{(w_n^0)^2,(w_n^1)^2,...,(w_n^{n/2-1})^2\}=\{(w_{n/2}^0)^2,(w_{n/2}^1)^2,...,(w_{n/2}^{n/2-1})^2\}$

  只需要计算 $A^{[0]}, A^{[1]}$ 的 (n/2) 次单位根

• 所以，计算 $A(x)=A^{[0]}(x^2)+xA^{[1]}(x^2)$ 在 $x\in\{w_n^0,w_n^1,...,w_n^{n-1}\}$ 处的值

  分治：相当于计算 $A^{[0]}(x), A^{[1]}(x)$ 在 $x\in\{w_{n/2}^0,w_{n/2}^1,...,w_{n/2}^{n/2-1}\}$ 处的值，这也是 DFT，可以递归地用 n/2 个点上的 FFT 算出

  合并：对于 $0 \le k \le \frac{n}{2}-1$

  • $A(w_n^k)=A^{[0]}(w_{\frac{n}{2}}^k)+w_n^kA^{[1]}(w_{\frac{n}{2}}^k)$
  • $A(w_n^{k+n/2})=A^{[0]}(w_{\frac{n}{2}}^{k+\frac{n}{2}})+w_n^{k+\frac{n}{2}}A^{[1]}(w_{\frac{n}{2}}^{k+\frac{n}{2}})=A^{[0]}(w_{\frac{n}{2}}^k) - w_n^kA^{[1]}(w_{\frac{n}{2}}^k)$
• 时间复杂度 $T(n)=2T(\frac{n}{2}+O(n))$，所以 $T(n)=O(n\text{log}n)$

递归 FFT

参考

上海科技大学 CS121 2020