Chiarimento su FFT

Question

So che c'è qualcosa di sbagliato con il seguente ragionamento, ma non sono sicuro di cosa si tratta.

La FFT:

1. dati due polinomi

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

   e

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

   è possibile calcolare i coefficienti del prodotto

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

   in tempo O(n log n ).

2. Quindi, dati due vettori (a_0, ..., a_n) e (b_0, ..., b_n) possiamo calcolare   la v_i = \sum j = 0 ^ k ( a_j b_{k-j}) vettore in tempo O(n log n) (incorporando i vettori di zeri.)

3. Tutto ciò premesso, dovremmo essere in grado di calcolare il prodotto scalare di A =(a_0, ..., a_n) e B =(b_0, ..., b_n) che è A.B = \sum_j=0 ^ n a_j b_j nel tempo O(n log n) dalla pre-elaborazione uno dei vettori dire B essere B' = (b_n, b_{n-1}, ..., b_1, b_0) poi calcolando la convoluzione come in 2. in O(n log n) tempo.

Se quanto sopra ragionamento è corretto, allora significa che siamo in grado di implementare Matrix Moltiplicazione di due matrici nxn in tempo O(n^2 log n ) calcolando il prodotto scalare in tempi O(n log n) tempo O(n).

Tuttavia, la migliore run-time per la moltiplicazione di matrici che sappiamo è di circa O(n^2.4) quindi questo sembra improbabile che sia vero, che probabilmente significa di dei passi 1,2, o 3 non è corretto.

Answer 1

Ci sono voci n^2 nel prodotto, non n e così questo algoritmo sarebbe O(n^2 * n * log n) = O(n^3 log n).

E il miglior algoritmo per calcolare il prodotto scalare è O(n), non O(n log n). Ecco perché l'algoritmo naive per matrici moltiplicazione è O(n^3). (E 'prodotto scalare n^2 che può essere fatto in tempo O(n)).

Answer 2

Mi chiedo perché si tratta di un risultato che al punto 3 è possibile calcolare il prodotto scalare in O (n log n) in quanto è ben noto che il prodotto scalare può essere calcolato in O (n)? Anche passo 2 si presenta come il tempo lineare, invece di O (n log n) passo?

Anche la conclusione circa O (n ^ 2 log n) non segue logicamente. Non si può prendere il prodotto scalare O (n) volte con conseguente matrice AB --- per quanto ne so si deve prendere O (n ^ 2) Prodotti di punti, portando a (per l'analisi) O (n ^ 3 log n), che è inferiore a O standard (n ^ 3). Questo è a causa della vostra strana O (n log n) dot risultato prodotto.