傅里叶变换

卷积就是两多项式相乘结果的系数；多项式有“点值表示”，因为n维多项式有n个点值对就可求解得系数；离散傅里叶变换DFT是求值：计算多项式在n个单位复根处的值；快速傅里叶变换FFT是用分治法计算DFT

x = f(ω0)= cos(ω0t) + i sin(ω0t) = e^{iω0t}，神奇的欧拉公式，x^k = f(kω0) = cos(kω0t) + i sin(kω0t) = e^{ikω0t}

其中ω0=2π/T=2πf，T是周期

时域信号相乘，相当于频域做卷积

两个向量相乘，积的模等于各向量模的积，积的辐角等于各向量的辐角的和。

屏幕快照_2017-01-16_22-32-25.png

把函数展开成无数余弦正弦的和，即把函数线性变换到余弦正弦基的空间

类似的，泰勒展开是把函数线性变换到多项式基的空间

* 《算法导论》

🧠 Brain