algorithm - 关于 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) 时间。

如果上述推理是正确的，那么这意味着我们可以通过计算点在 O(n^2 log n ) 时间内实现两个 nxn 矩阵的矩阵乘法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) 时间内完成)。