FFT 的澄清

Question

我知道以下推理有问题，但我不确定它是什么。

快速傅里叶变换：

1. 给定两个多项式

   A = a_0 + a_1 x + a_2 x^2 + ... + a_n x^n

   和

   B = b_0 + b_1 x + b_2 x^2 + ... + b_n x^n

   您可以计算乘积的系数

   AB = \sum _k = 0 ^ 2n ( \sum _ j = 0 ^ k (a_j b_{k-j}))x^k

   在 O(n log n ) 时间。

2. 所以给定两个向量 (a_0, ..., a_n) 和 (b_0, ..., b_n) 我们可以计算矢量 v_i = \sum j = 0 ^ k ( a_j b_{k-j}) 在 O(n log n) 时间（通过将向量嵌入零。）

3. 鉴于上述，我们应该能够计算出点积 A =(a_0, ..., a_n) 和 B =(b_0, ..., b_n) 这是 A.B = \sum_j=0 ^ n a_j b_j 在 O(n log n) 通过预处理向量之一来计算时间 B 成为 B' = (b_n, b_{n-1}, ..., b_1, b_0) 然后按照 2 中的方式计算卷积。在 O(n log n) 时间。

如果上述推理是正确的，那么这意味着我们可以实现两个的矩阵乘法 nxn 矩阵在 O(n^2 log n ) 通过计算点积来计算时间 O(n log n) 时间 O(n) 次。

然而，我们知道矩阵乘法的最佳运行时间大约是 O(n^2.4) 所以这似乎不太可能是真的，这可能意味着步骤 1,2 或 3 是不正确的。

Answer 1

有 n^2 产品中的条目，而不是 n 所以这个算法是 O(n^2 * n * log n) = O(n^3 log n).

计算点积的最佳算法是 O(n), ， 不是 O(n log n). 。这就是为什么矩阵乘法的朴素算法是 O(n^3). 。（它是 n^2 可以完成的点积 O(n) 时间）。

Answer 2

我想知道为什么在步骤 3 中你可以在 O(n log n) 时间内计算点积，因为众所周知，点积可以在 O(n) 时间内计算出？另外，第 2 步看起来像是线性时间，而不是 O(n log n) 步骤？

此外，关于 O(n^2 log n) 的结论也不符合逻辑。您不能采用 O(n) 次点积来得到 AB 矩阵——据我所知，您必须采用 O(n^2) 次点积，从而得出（根据您的分析）O(n^ 3 log n) 低于标准 O(n^3)。这是因为你的 O(n log n) 点积结果很奇怪。