分治法

分治法（Divide and Conquer）是计算机科学中最经典的算法设计思想之一，将复杂问题分解为多个相同类型的子问题，递归求解后再合并结果。FFT实现 $O(N^2)$ 到 $O(N\log N)$ 跨越的根本方法论。

在FFT中的应用

FFT将原始信号按照"奇数位置"和"偶数位置"拆分成两个长度为N/2的子信号，处理这两个较短信号的计算量远远小于直接处理原信号。FFT会继续对子信号进行"对半拆分"，直到信号被拆解为最基本的两个点。通过层层对半折叠和结果的精妙复用，成功将整体的计算复杂度从 $O(N^2)$ 压缩到了 $O(N\log N)$。