咨询：各维度含{N1,N2…Nn}点的n维离散傅里叶变换计算复杂度

好问题！咱们一步步来拆解这个问题，先从朴素的n维离散傅里叶变换（DFT）说起，再延伸到快速傅里叶变换（FFT）的情况：

1. 朴素n维DFT的计算复杂度 #

首先明确：实际计算n维DFT时，最常用的方法是逐维度计算1维变换，比直接暴力计算所有输入输出的卷积高效得多。

已知1维朴素DFT的复杂度是O(N²)（N为1维数据集大小），对于各维度点数为{N₁, N₂, ..., Nₙ}的n维数据，总点数N = N₁ × N₂ × … × Nₙ：

• 对第i个维度来说，我们需要对剩下n-1维组成的「切片」做1维朴素DFT。每个切片大小为Nᵢ，一共有N/Nᵢ个这样的切片（总点数除以当前维度点数就是切片数量）。
• 每个1维朴素DFT的复杂度是O(Nᵢ²)，因此第i个维度的总计算量为O( (N/Nᵢ) × Nᵢ² ) = O(N × Nᵢ)。
• 把所有维度的计算量累加，总复杂度就是：

  O(N × (N₁ + N₂ + ... + Nₙ))
  

  展开写就是 O( (N₁N₂…Nₙ) × (N₁ + N₂ + ... + Nₙ) )

举个2维的例子：假设是N₁×N₂的矩阵，总复杂度就是O(N₁N₂(N₁+N₂))——先对每行（N₁个点）做O(N₁²)的变换（共N₂行），得到O(N₂N₁²)；再对每列（N₂个点）做O(N₂²)的变换（共N₁列），得到O(N₁N₂²)，两者相加正好匹配上面的公式。

2. n维快速傅里叶变换（FFT）的计算复杂度 #

如果用FFT加速每个维度的计算（1维FFT的复杂度是O(N log N)），同样采用逐维度的方法：

• 对第i个维度，每个切片的1维FFT复杂度是O(Nᵢ log Nᵢ)，一共有N/Nᵢ个切片，因此第i个维度的总计算量为O( (N/Nᵢ) × Nᵢ log Nᵢ ) = O(N × log Nᵢ)。
• 累加所有维度的计算量，总复杂度就是：

  O(N × (log N₁ + log N₂ + ... + log Nₙ))
  

  利用对数的乘积性质，log N₁ + log N₂ + ... + log Nₙ = log(N₁×N₂×…×Nₙ) = log N，所以这个复杂度也可以简化为更简洁的形式：

  O(N log N)
  

  这里的N依然是n维数据的总点数。

还是用2维举例：总复杂度就是O(N₁N₂ (log N₁ + log N₂)) = O(N₁N₂ log(N₁N₂))，也就是O(N log N)，和简化后的公式完全一致。

内容的提问来源于stack exchange，提问作者Herpes Free Engineer