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）點積結果。