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)我们可以O(n log n)时间计算 矢量v_i = \sum j = 0^k (a_j b_{k-j})（由零嵌入载体。）

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)然后计算卷积如在O(n log n)时间在2。

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

但是，我们知道矩阵乘法的最佳运行时间大约是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）点积结果。