两个长度接近n的系数数组做朴素卷积，需要约n²次乘法。把其中一个数组机械地切成两半，仍然需要与另一个数组的每个元素相乘，总工作不会减少。有效分治需要找到可以共享的中间结果，而不只是增加递归调用。

FFT利用单位根的成对结构共享多项式求值。本篇从卷积开始推导这项结构，再用选择问题对照另一种分治：不是加速合并，而是只递归进入包含目标的一边。两者的递推不能混写。

卷积等价于多项式乘法

输入实数系数数组a、b，长度分别为p、q；输出c长度p+q−1，其中

ck=∑i+j=kaibj.c_k=\sum_{i+j=k}a_i b_j.

把A(x)=Σa_i x^i、B(x)=Σb_j x^j相乘，c正是乘积系数。空数组在教学接口中代表没有系数，任意一方为空时返回空结果；这个约定单独处理，避免长度公式产生负数。

朴素算法对每对(i,j)把a_i b_j加到c[i+j]。在单位成本实数运算模型下，乘法p q次，累加同阶。这是可复跑的独立参照，也直接体现正确性：每个应进入第k项的乘积恰好被访问一次。

另一种表示是多项式在足够多不同点上的值。逐点相乘很便宜；困难在于从系数快速求值，以及从值快速恢复系数。如果普通地在N个点分别代入，每点O(N)，并没有摆脱二次成本。

复数只需用到旋转与乘法

复数写成u+iv，i²=−1。单位圆上的e^(iθ)=cosθ+i sinθ，乘法把角度相加。取ω_N=e^(−2πi/N)，它满足ω_N^N=1；ω_N^0到ω_N^(N−1)是N个不同的单位根。

本文前向DFT采用负号：输出第k项为A(ω_N^k)。逆变换使用相反的正号，最后除以N。正负号也可以整体反过来，条件是前后约定配对；不能把两份来源的不同符号约定拼接。

恢复成立的核心恒等式是单位根正交性：Σ从k=0到N−1的ω_N^(k r)，当r是N的倍数时等于N，否则为0。后一种情况是公比不等于1、首尾抵消的有限等比级数。把前向和代入逆向和，每个系数之外的交叉项都消失，只留下N倍原系数。

偶数项与奇数项共享平方后的点

将多项式拆为

A(x)=Aeven(x2)+xAodd(x2).A(x)=A_{even}(x^2)+x A_{odd}(x^2).

当N为2的幂，ω_N的平方就是ω_(N/2)，而相隔N/2的两个求值点互为相反数。两个点平方后相同，所以只需递归计算两个长度N/2的变换。

令E_k、O_k分别为偶数系数和奇数系数的变换，则对0≤k<N/2：

Yk=Ek+ωNkOk,Yk+N/2=Ek−ωNkOk.Y_k=E_k+\omega_N^k O_k,\qquad Y_{k+N/2}=E_k-\omega_N^k O_k.

同一个乘积t=ω_N^k O_k用于两个输出。这一次合并称为蝶形：一项复乘、两项复加或复减，不把计算单位根的三角函数调用藏进这个口径。

长度1时变换等于输入。由子问题正确性和上面分解式归纳，每轮合并得到正确的N点DFT。沿02篇的递归树分析，T(N)=2T(N/2)+Θ(N)，故最坏Θ(N log N)次算术操作；单个变换的蝶形数恰为(N/2)log₂N，N=1时为0。

递归切片实现会产生额外数组，但深度优先执行时各层同时存活的总数组长度形成几何级数，峰值辅助空间仍为O(N)，栈深O(log N)。累计分配与拷贝工作则应计入O(N log N)，不能因为峰值线性就宣布没有拷贝成本。

为什么必须补零到乘积长度

选择2的幂N≥p+q−1，把两个数组补零到N。分别前向变换，逐点相乘，再逆变换，截取前p+q−1项。

求值点满足x^N=1，所以N点变换直接对应模x^N−1的循环卷积。补零保证真实乘积次数小于N，没有高次项折回低次项，因此恢复的是普通线性卷积。

若a=b=[1,1]却使用N=2，真实乘积为[1,2,1]；x²项折回常数项，循环结果成为[2,2]。这不是舍入误差，而是模型选错。增大浮点精度无法修复补零长度不足。

三次变换加N次逐点复乘和N次逆归一化，算术操作总阶O(N log N)，其中N小于2(p+q−1)，长度边界单独处理。这里讨论的是确定性操作计数，不是期望或高概率界。

代数证明没有消除浮点误差

上述等式在精确复数运算下成立。教学实现用有限精度浮点数，单位根近似、乘加舍入和消去都会影响结果。实数输入的逆变换还可能带有很小的虚部残差。

数值检查分别记录相对朴素精确整数参照的最大绝对实部误差，以及最大虚部残差。它们不是同一量：虚部小不保证实部正确，抵消严重时相对误差也可能很大。绝对误差阈值必须结合输入幅值和用途选择。

若要把结果四舍五入恢复整数，需要先证明每个系数误差严格小于1/2。小规模样例误差小并不提供任意长度、任意整数幅值的保证。很大的整数甚至在转换为浮点数时就失去低位；本实现返回近似值，不自动把它标成精确整数乘法。超过浮点可表示范围的输入不在本篇验证范围内。

选择问题减少的是递归分支

寻找第k小元素时，按枢轴划分后只需进入包含目标的一侧；重复值用小于、等于、大于三段区分。若选中等值段即可结束，不必继续排序其余元素。

每轮均匀随机选择枢轴，对任意固定输入有期望O(n)时间；但每次恰好选到极端元素仍可能产生Θ(n²)工作。随机枢轴的期望结论不是最坏保证，也不能用“通常各半”代替对随机选择的分析。

五个一组的median-of-medians选择各组中位数，再递归选这些中位数的中位数作为枢轴，能排除两侧各约3n/10个元素。最坏递推是T(n)≤T(ceil(n/5))+T(7n/10+O(1))+O(n)，因两个比例之和小于1而得O(n)。分组不完整和小n由常数基例吸收。

FFT递归两个半规模子问题并用线性合并共享求值；选择算法付线性划分成本后，只保留目标侧，或额外花成本保证枢轴质量。识别真正减少的工作，才知道应该证明哪条递推。本文不新增选择实现，也不从卷积实验推断选择算法性能。

可复跑检查

教学实现位于examples/advanced-algorithms/convolution.py。fft(values,inverse=False)只接受非空2幂长度，非法长度抛ValueError；convolve(a,b)自动补零，返回近似实数系数、FFT长度、统计和完整补零结果的最大虚部残差。输入须为能用于有限精度复数运算的有限数值，不支持用NaN或无穷定义代数卷积。仓库根目录运行：

1
python3 examples/advanced-algorithms/check_convolution.py

独立朴素参照用Python整数逐项乘加，对本次整数输入给出精确系数。实际枚举1600个短数组对，最大绝对误差为2.220446049250313e−16；6个复数往返用例最大误差为3.972054645195637e−15，另验证6个非法长度拒绝和一个实数输入。

固定种子20260920的最大样例输入长度128、129，补零N=256。三次变换合计3072个蝶形、6144次数据复加减、3072次数据复乘，另外生成3072个根、做256次逐点复乘和256次逆归一化除法。根生成包含自身的角度运算与复指数调用，未计为数据复乘；这种计数不能当作CPU指令数。

这一样例的实部最大绝对误差为3.410605131648481e−13，虚部残差为5.314753590106738e−13。全部十组规模的真实输出保存在examples/advanced-algorithms/results/convolution.json。这是本机浮点运算的实际误差记录和教学操作计数，没有测量运行时间；断言阈值只用于这些有限输入，不是对所有输入的误差定理。

练习

  1. 对a=[1,2]、b=[3,4]手算线性卷积，比较N=2的循环卷积与N=4补零卷积。指出每个折回项来自哪个多项式幂次。
  2. 假定实现得到近似整数卷积，最大观察误差为0.001。说明这个有限观察为什么不能支持任意输入直接取整，并写出安全恢复整数所需的逐系数误差条件。

参考资料