快速傅里叶变换，是快速计算序列的离散傅里叶变换或其逆变换的方法。傅里叶分析将信号从原始域转换到频域的表示或者逆过来转换。FFT会通过把离散傅里叶变换矩阵矩阵分解为稀疏矩阵因子之积来快速计算此类变换。 因此，它能够将计算DFT的计算复杂性理论从只用DFT定义计算需要的
O
{\displaystyle O}
，降低到
O
{\displaystyle O}
，其中
n
{\displaystyle n}
为数据大小。
1
蝶形结或蝶形网络是快速傅里叶变换算法中的组成单位，将原本的较大点数的离散傅里叶变换，拆成较小点数的离散傅立叶运算组合，反之亦然，其中蝶形结架构的n点离散傅里叶变换并不一定需要满足为点数 n = 2 的条件。蝶形结其名来自于底数为2的信号流图形似蝴蝶外观。这个词最早是由1969年一份MIT的技术性报告提到，类似的架构也出现于维特比算法中，用于寻找隐匿层中最有可能的序列。
颂哈吉-施特拉森算法是渐近快速的大整数乘法算法。是由阿诺德·颂哈吉和沃尔克·施特拉森在1971年发明。若针对二个n位元的整数，其运行的位元复杂度，若以大O符号表示，是
O
{\displaystyle O}
。算法使用在有2+1个元素的环上的迭代快速傅里叶变换，这是一种特别的数论转换。
雷德算法是一种于1968年由麻省理工学院林肯实验室之查尔斯·M·雷德提出的快速傅里叶变换算法。当讯号的资料点数量为质数时，此算法可借由将离散傅立叶转换重新表示为圆周折积，快速计算出该讯号之离散傅立叶转换结果。另一种称为Chirp-Z转换的作法也是透过类似的方式将离散傅立叶转换改写为折积完成转换，且同样限制讯号长度需为质数。
在数学中，欧德里兹科-肖恩哈格算法是一个用于评估多点上黎曼ζ函数的值的快速算法，由发现。其主要思想是使用快速傅里叶变换加速N个等O间隔的值的有限狄利克雷级数的计算，从O步减少到O步。黎曼-西格尔公式，用于计算虚部为T点上黎曼ζ函数的值，使用约N = T项的有限狄利克雷级数，所以要找到N个黎曼ζ函数的值时，它将加速约T倍。这将找到虚部不超过T的ζ函数零点所需的时间从大约T步减少到了大约T步。
颂哈吉-施特拉森算法是渐近快速的大整数乘法算法。是由阿诺德·颂哈吉和沃尔克·施特拉森在1971年发明。若针对二个n位元的整数，其运行的位元复杂度，若以大O符号表示，是
O
{\displaystyle O}
。算法使用在有2+1个元素的环上的迭代快速傅里叶变换，这是一种特别的数论转换。
Mini wiki
