Aclaración sobre FFT

Question

Sé que hay algo mal con el siguiente razonamiento, pero no estoy seguro de lo que es.

La FFT:

1. dadas dos polinomios

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

   y

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

   Puede calcular los coeficientes del producto

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

   a tiempo O(n log n ).

2. Así que les da dos vectores (a_0, ..., a_n) y (b_0, ..., b_n) podemos calcular   el vector v_i = \sum j = 0 ^ k ( a_j b_{k-j}) en el tiempo O(n log n) (mediante la incorporación de los vectores en ceros.)

3. Dado lo anterior, debemos ser capaces de calcular el producto escalar de A =(a_0, ..., a_n) y B =(b_0, ..., b_n) que es A.B = \sum_j=0 ^ n a_j b_j en el tiempo O(n log n) por preprocesamiento uno de los vectores decir B ser B' = (b_n, b_{n-1}, ..., b_1, b_0) entonces el cálculo de la convolución como en 2. En O(n log n) hora.

Si el razonamiento anterior es correcta, entonces eso significa que podemos aplicar multiplicación de matrices de dos matrices nxn en tiempo O(n^2 log n ) calculando el producto escalar en tiempos O(n log n) tiempo O(n).

Sin embargo, el mejor tiempo de ejecución para la multiplicación de matrices que sabemos se trata de O(n^2.4) por lo que este parece poco probable que sea cierto, lo que probablemente significa de los pasos de 1,2 o 3 es incorrecta.

Answer 1

Hay entradas n^2 en el producto, no n y por lo que este algoritmo se O(n^2 * n * log n) = O(n^3 log n).

Y el mejor algoritmo para el cálculo de productos escalares es O(n), no O(n log n). Es por eso que el algoritmo ingenuo para la multiplicación de matrices es O(n^3). (Es n^2 productos escalares que se pueden hacer en el tiempo O(n)).

Answer 2

Me pregunto por qué es un logro que en el paso 3 se puede calcular el producto escalar en O (n log n), puesto que es bien sabido que producto escalar se puede calcular en tiempo O (n)? También el paso 2 se ve como el tiempo lineal en lugar de O paso (n log n)?

También la conclusión acerca de O (n ^ 2 log n) no se sigue lógicamente. No se puede tomar el producto punto O (n) veces resulta en la matriz AB --- por lo que sabe que tiene que tomar O (n ^ 2) productos de punto, lo que (según su análisis) O (n ^ 3 log n), que es inferior a S estándar (n ^ 3). Esto es debido a su extraña O (n log n) dot resultado producto.