离散傅立叶变换（DFT）广泛应用于几乎所有科学和工程领域。在信号处理领域中,傅立叶变换是最重要的信号处理工具。在通信领域,傅立叶变换大量应用于正交频分复用（OFDM）系统中。然而,直接计算傅立叶变换是一个计算强度很大的工作。所以,高效计算强度小的计算算法是必需的。快速傅立叶变换（FFT）就是一类高效计算强度小的傅立叶变换的计算算法。麻省理工的Johnson和Frigo教授提出的修正的分裂基FFT（MSRFFT）算法是2014之前计算复杂度最低的算法（2014我们提出2个计算复杂度更低的算法）。为了提高该算法的实用性,通过分析MSRFFT,我们发现MSRFFT有一组分解不是必需的。另外,通过适当的变换,可以减少查表访问旋转因子的次数。因此,我们对该算法进行了完善,将该算法的4个分解过程只保留了3个（但计算复杂度保持不变）,将MSRFFT所需要的5/8N-2次因子访问次数减少到只要15/32N-2次。针对长度为N= 6^m的DFT,我们提出了基-3/6FFT算法来对其进行计算分解,在计算分解的同时对带因子的子DFT进行旋转变换,使得旋转因子的下标不包括因子3,从而减少算法的计算复杂度。针对长度为q×2^m的DFT,我们通过执行2^m个长度为q的DFT将该DFT分解成q个长度为2^m的子DFT。该方法通过旋转变换将带因子（wⁿ）_N,w_N^N/4+n,...,W_N^{（q-1）N/4+n}的(共计q0项放在一列组成一个长度为q的子DFT,抽取该q个旋转因子的公共因子（wⁿ）_N使得该子DFT变成带常数因子的DFT（SDFT）。SDFT将会使用我们提出的方法来高效实现,减少其计算复杂度。由于长度为q的FFT的计算精度比2的幂次方的FFT差,我们对以上算法进行改进,通过旋转变换将带因子为Wⁿ_q的（共计2^m个）项放在一列组成一个长度为2^m的子DFT,该SDFT同样可以高效实现,其计算复杂度和原算法一样,精确度提高了。针对长度为N= 2^m的DFT,我们提出了四个算法。这四个算法,都是在MSRFFT算法的基础上提出来的。我们的算法克服了 MSRFFT算法的缺点,将MSRFFT算法的因子抽取方法扩展到复数。相比于分裂基FFT（SRFFT）,我们所提四个计算2^m长度FFT算法中的其中二个算法在计算复杂度、计算精度和旋转系数计算或查表次数三个方面的性能得到了提高。其它两个计算2^m长度FFT算法是目前已经出版的算法中计算复杂度最低的算法。由于L-型的蝶的算法具有较高的实现复杂度,因此我们提出了一个新的实现方法,将一个L-型蝶分解成几个类似于基-2 FFT的蝶的执行单元（BU-2）,将一个L-型蝶块分解成几个BU-2块。所有分裂基系列FFT算法都可以使用这个方法象Cooley-Tukey算法一样递推实现。采用这个方法,我们用递推的方法实现了第2章的简化的修正的MSRFFT算法和第6章所提的计算长度N=q× 2^m的FFT算法。通过比较我们发现:（1）递推实现的MSFFT在DFT较小比其它算法速度快,但当DFT较大时,所需时间会会急剧增加,因为MSFFT需要的内存比其它算法要多。（2）递推实现的所提计算长度N = q × 2^m的FFT算法,与其它算法相比所需要的时间相对要少;和FFTW相比,当DFT较小时,我们所提算法要比FFTW快,但当DFT较大时,我们的算法就比FFTW慢,因为我们的程序没有进行内存优化。剪切FFT就是针对输入信号数目和/或输出信号数目远小于DFT长度的一类优化算法。该类算法采用减少或消除标准FFT的多余操作的方式来达到提高效率的目的。考虑到剪切FFT的蝶不再对称的这一特点,我们提出四种基于共轭因子的方法来进行FFT剪切,减少剪切FFT算法在输入和/或输出阶段的计算复杂度。和其它剪切FFT算法相比,我们所提四种算法减少了计算复杂度。多序列比对（MSA）是生物信号学中最重要的分析工具之一。有一个叫MAFT的MSA程序采用FFT来进行序列相似性的计算,识别相似区域,减少序列比对的解空间,是序列比对精度最高的MSA程序中速度最快的程序。为了进一步完善MAFFT的计算效率,我们对MAFFT的序列相似性的计算方法进行了三个方面的修正。首先,基于复数的氨基酸和核苷酸表示被使用在修正的相关系数计算方案中,代替了原来基于实数的表示。由此,相比于原MAFFT方案,一半的内存和一多半的计算可以节省。其次,线性卷积代替了循环卷积来计算氨基酸和核苷酸队列的相关系数,在计算最优路径的过程中,更多的同态区域将会被发现。再其次,我们设计一个FFT算法来高效计算线性卷积。所设计FFT算法基于共轭FFT（CPFFT）,不需要执行队列的排序。该FFT还是一个新颖的剪切FFT,他的输出只需要实数。模拟结果显示修正的方案计算队列的相关系数的速度是MAFFT的3倍。总之,我们提出的这几个快速算法是同类算法计算复杂度最低的算法。提出的执行方法可以将所有分裂基FFT算法进行递推执行。提出的修正的MAFFT算法,将MAFFT的速度提高了2～3倍。