快速傅里叶变换FFT为什么必须是2^n呢?

快速傅里叶变换FFT为什么必须是2^n呢?

不一定，亦存在不需指定为$2^n$的FFT。之所以通常的FFT需要指定为$2^n$个点，大概是因为这些原因：1. 最简单的FFT实现基于一个折半（$n \to \frac{n}{2}$）的递归。如此，我们当然需要点的个数为$2$的幂。2. 在以上基础上，一般需要使用FFT的场合，对点数并没有强制限定。即，即使点数不是$2$的幂，可以增加一些平凡（一般是值为$0$的）点凑出一个$2$的幂，然后进行运算，如此不影响算法的执行。（当然，有一些场合下，因为某些外部的要求，并不能使用该方法）3. $2$的幂对于计算机而言是“喜欢的”。