关于FFT
  • 板块学术版
  • 楼主strcmp
  • 当前回复6
  • 已保存回复6
  • 发布时间2022/1/21 19:55
  • 上次更新2023/10/28 11:38:06
查看原帖
关于FFT
551861
strcmp楼主2022/1/21 19:55

背景:本蒟蒻正在学习FFT,BFS了七八篇博客,但基本上关于为什么在求值时要使用单位复数根只是简略的过了一下,懵逼了一个下午(当然也可能是我悟性太差了

求助各位神犇

1,为什么FFT求值时要使用单位复数根?

2,为什么用了单位复数根,计算每个子问题的时候只需要计算一半?(蒟蒻看了亿堆博客,似乎是因为 wnkw_{n}^{k}wnk+n2w_{n}^{k+\frac{n}{2}} 只有符号不同,但不知道理解有没有偏差)

非常感谢OrzOrzOrz

2022/1/21 19:55
加载中...