算法与复杂性相关笔记。 分治

Chapter 2. Divide-and-Conquer Algorithms

Recurrence relations

Master theorem:

$$T(n)=a T(\lceil n / b\rceil)+O\left(n^{d}\right)$$

for some constants (a>0) , (b>1) ,and (d ≥0) , then

$$T(n)= \begin{cases}O\left(n^{d}\right) & if d>log _{b} a \\ O\left(n^{d} log n\right) & if d=log _{b} a \\ O\left(n^{log _{b} a}\right) & if d<log _{b} a .\end{cases}$$

d代表非递归部分（即每次递归调用之外的操作）的时间复杂度的指数。

Example: 整数乘法的分治算法

$$T(n)=3 T(n / 2)+O\left(n\right)$$

FFT

基本思想: 利用分治方法使得多项式相乘算法的复杂度降为O(n logn)

具体实现：借用多项式的点值表示法（n+1个点确定一个n维多项式）的乘法可以在O(n)内完成，将多项式相乘转为点值表示法相乘再转回原系数表示

fft数学公式：

$$\begin{aligned} \begin{bmatrix} y_0 \\ y_1 \\ y_2 \\ \vdots \\ y_{n-1} \end{bmatrix} &= \begin{bmatrix} W_n^{0\cdot0} & W_n^{0\cdot1} & W_n^{0\cdot2} & \cdots & W_n^{0\cdot(n-1)} \\ W_n^{1\cdot0} & W_n^{1\cdot1} & W_n^{1\cdot2} & \cdots & W_n^{1\cdot(n-1)} \\ W_n^{2\cdot0} & W_n^{2\cdot1} & W_n^{2\cdot2} & \cdots & W_n^{2\cdot(n-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ W_n^{(n-1)\cdot0} & W_n^{(n-1)\cdot1} & W_n^{(n-1)\cdot2} & \cdots & W_n^{(n-1)\cdot(n-1)} \end{bmatrix} \begin{bmatrix} x_0 \\ x_1 \\ x_2 \\ \vdots \\ x_{n-1} \end{bmatrix} \end{aligned}$$

我们设计了快速傅里叶变换（FFT），它可以在 的时间内将系数转换为值，其中点 是复数的 (n) 次单位根：

$$(1, \omega, \omega^2, \dots, \omega^{n-1}).$$

即：

$$\langle \text{value} \rangle = \text{FFT}(\langle \text{coefficients} \rangle, \omega).$$ $$\langle \text{coefficients} \rangle = \frac{1}{n} \text{FFT}(\langle \text{values} \rangle, \omega^{-1}).$$

快速傅里叶变换（FFT）将任意 (n)-维向量（即系数表示）乘以 (n \times n) 矩阵：

$$M_n(\omega) = \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega & \omega^2 & \cdots & \omega^{n-1} \\ 1 & \omega^j & \omega^{2j} & \cdots & \omega^{(n-1)j} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega^{n-1} & \omega^{2(n-1)} & \cdots & \omega^{(n-1)(n-1)} \end{bmatrix}.$$

矩阵的第 (j, k) 元素（从零开始计数）为 。

逆公式：

$$M_n(\omega)^{-1} = \frac{1}{n} M_n(\omega^{-1}).$$

快速傅里叶变换详解