算法设计与分析.05.分治算法 (3)
分治 (3)
convolution and FFT
- 傅里叶定理
- Any (sufficiently smooth) periodic function can be expressed as the sum of a series of sinusoids.
- 欧拉定理
- 好处:Sum of sine and cosines = sum of complex exponentials
\[ e^{ix}=\cos x+i\sin x \]
- 变换的作用
- 时域上复杂的信息,频域上可能很简单
- FFT:Fast Fourier transform
- 时域频域之间的快速变换
- Fast way to multiply and evaluate polynomials
参数表示
- Univariate polynomial(一元多项式)
- Addition:\(O(n)\)
- Evaluation(求值)
- Horner’s method
- Multiplication (linear convolution)
- Brute Force:\(O(n^2)\)
点表示
- point-value representation
- 一元 n 次多项式有 n 个复数根
- n-1 次多项式被 n 个不同的点唯一决定
- 因此一个 n-1 次多项式能够使用 n 个点表示
操作
- 加法:\(O(n)\)
- 点对点加法(\(n\) 个点)
- 乘法:\(O(n)\)
- 点对点乘法(\(2n\) 个点)
- 如何得到这些点的值?
- 求值:拉格朗日乘子法
- trade off
- 是否有表示方式,乘法和求值都比较快?
Brute Force
参数表示转化为点表示
- Brute-Force:\(O(n^2)\)
- 两种方式
- 矩阵乘向量
- Horner’s method
点表示转化为参数表示
- Brute-Force:\(O(n^3)\)
- 高斯消去法求解 \(\mathrm{a}\)
分治
- 如何多项式求值?
- 两种方式
参数表示转化为点表示
- 奇偶拆分
- 选择 \(x=i,-i,1,-1\),那么可以通过两个子问题计算,就算出 \(A(x)\)
- 选择 \(x_k=\omega^{k}\) 为 1 的 n
次单位根
- \(x^n=1\)
- \(\omega=e^{2\pi i/n}\)
- n/2 次单位根:\(v=e^{4\pi i/n}=\omega^2\)
算法
- \(n\) 表示 \(n\) 次单位根
- 使用奇偶拆分
\[ 0\le k<n/2 \]
\[ \begin{aligned} y_k &=A(\omega^{k})\\ &=A_{\text{even}}(w^{2k})+w^{k}A_{\text{odd}}(\omega^{2k})\\ &=A_{\text{even}}(v^{k})+w^{k}A_{\text{odd}}(v^{k})\\ \end{aligned} \]
\[ \begin{aligned} y_{k+n/2} &=A(\omega^{k+n/2})\\ &=A(-\omega^{k})\\ &=A_{\text{even}}(w^{2k})-w^{k}A_{\text{odd}}(\omega^{2k})\\ &=A_{\text{even}}(v^{k})-w^{k}A_{\text{odd}}(v^{k})\\ \end{aligned} \]
复杂度
\[ T(n)=2T(\dfrac{n}{2})+\Theta(n)\Rightarrow T(n)=\Theta(n\log n) \]
过程
- 发现最后的顺序是按照比特位的逆序
1 | 000 -> 000 |
矩阵形式
点表示转化为参数表示
- 矩阵求逆
- 能够显式求逆
- 证明是逆矩阵
算法
- 注意最终的结果需要除以 \(n\)
FFT 总结
- 第一步两次 FFT 形成 2n 个点
- 把多项式的高位系数看成 0
- iFFT 的结果,\(c_{2n-1}=0\)
FFT 应用
- 一个较好的实现
- Fastest Fourier transform in the West
- 特点
- Core algorithm is an in-place, nonrecursive version of Cooley–Tukey
- 根据硬件编译形成不同的版本
- \(O(n\log n)\) even when \(n\) is prime
- Multidimensional FFTs
- Parallelism
大整数乘法
- \(a=a_{n-1}\cdots a_0,\;b=b_{n-1}\cdots b_0\)
- 构造两个 \(n-1\) 次多项式,使用 FFT 求解
- 结果令 \(x=2\) 即可
- \(O(n\log n)\) 次浮点运算
- 注意这里的计算有很多浮点运算,需要保证精度
3-SUM 问题
- 是否存在三元组 \(i\in X,j\in Y,k\in Z\),使得 \(i+j=k\),\(X,Y,Z\) 是整数集合,各含有 \(n\) 个元素
- 假定:所有整数都在 \([0,m]\) 范围内
- 实现 \(O(m\log m+n\log n)\)
算法
- \(O(m\log m+n)\)
- \(c_k>0\):有 \(c_k\) 种选择 \(i,j\) 的方式,实现 \(i+j=k\)