ω \omega ω 的计算
ω n 1 \omega_n^1 ωn1 的计算
考虑单位圆，
ω
n
1
\omega_n^1
ωn1 为：
也就是：
注：op为判断当前为dft还是idft
ω n i \omega_n^i ωni 的计算
当要计算 ω n i \omega_n^i ωni 时，只需要在 ω n i − 1 \omega_n^{i-1} ωni−1 基础上乘 ω n 1 \omega_n^1 ωn1 即可
初始时实现奇偶翻转
转化为二进制反正
在程序开始，可以先进行好翻转。
- 初始：
0 1 2 3 4 5 6 7 - 最终：
0 4 2 6 1 5 3 7
发现其实是对二进制进行翻转，考虑其最后一位的翻转过程：
先对前面进行翻转，再补上第一位：
翻转对称性
可以发现，翻转过程具有对称性，所以可以直接暴力翻转：
