algorithm - 关于 FFT 的说明

Question

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

FFT：

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. 鉴于上述情况，我们应该能够通过预处理其中一个向量来计算 和 的点积，然后按时间计算2.A =(a_0, ..., a_n)中的卷积。B =(b_0, ..., b_n)A.B = \sum_j=0 ^ n a_j b_jO(n log n)BB' = (b_n, b_{n-1}, ..., b_1, b_0)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) 点积结果。