高级算法设计与分析 学习笔记14 FFT
本章我们研究多项式乘法。
我们直接乘，时间复杂度是n^2。使用FFT则可以变成nlgn
编辑
可以看到两个n°的多项式，我们直接乘，每种组合都要试一遍，就会要是n^2遍
编辑
那么要怎么加速呢？
编辑
首先多项式可以通过这种方法来表示
记录下n个点，想要原版形式的话就解矩阵方程吧。
编辑
编辑
编辑
不过这种表示法太奇怪了，能不能来经典形式的？
编辑
这里解释一下单位根：
单位根是复数分析中的一个概念，它是指满足以下等式的复数 ωω：
ω^n=1
这里的 n 是一个正整数，表示单位根的阶数。换句话说，单位根是一个复数，当它被提升到 n 次幂时，结果为1。单位根在复平面上的单位圆上均匀分布。
分治法！
Fn矩阵计算起来很简单：
