FFT的详解
背景知识
Fourier Series 指数形式
DFS : cofficient -> value
DFS的矩阵形式(Fourier matrix)
引入FFT
FFT可以理解为快速计算Fourier matrix(Discrete Fourier matrix)的一种算法,其本质是多项式求值算法。
ps:而其逆也就是IFFT，是解决插值问题。
为啥 计算Fourier matrix times c 和 多项式求值 关联起来了？
以下为Fourier matrix
和范德蒙德矩阵其实是一样的！
Fourier级数的指数展开，和多项式其实是差不多的，离散的指数展开，就相当于n个n次多项式，每一个多项式的未知数均是x^n=1的根
进而可以将DFS转换为本质的polynomial求值问题
polynomial求值
Part1
先来一个Big picture
🆗，那么接下来我们首先关注coeff ->value，也就是求值部分，FFT大放光彩的地方
对于多项式，不仅有系数表示，还有点值表示
系数表示
点值表示
点值表示下的多项式乘法:O(n), ...
大鸟转转转酒吧内部绝密档案
Welcome to BigBirdCircling Bar!
才不是Dicky Twister QAQ
🆗，那么这个文章是干嘛的呢
💖大鸟转转转作战记录(respect🚀！)：求生之路，batter field…
群聊骚话记录💋
典中典发言记录🀄
作战记录：
2021/7/24:求生之路
ok，这局谁最菜我不用多说了。
卡在了第三关----运输油桶，尝试了n次，在翔神的带领下，成功打通。
每次重开的时候，都要进电梯，然后zmk硕大的身躯填满了整个电梯间，zxr想开枪打玻璃，未曾想打中zmk，然后，然后就出现了！经典永流传！：
zmk：谁打我8点血！？影响整个大局！
典中典+1
2021/8/13:Apex
《真香》
hjb立大功捏
2021/8/19:Apex
fx,zmk双排竞技场，看数据，翔神输出依旧稳定1k+C位，em队友215挺拉但也海星，这时，当众人目光聚焦zmk的时候，出现了，典中典！
zmk:我打的侦察位！
高情商：打侦察位
低情商：咱这伤害还没215
不亏是大鸟转转转最帅的男人------zmk！
2021/8/24:无 ...
