Précision sur FFT

Question

Je sais qu'il ya quelque chose de mal avec le raisonnement suivant, mais je ne suis pas sûr de ce qu'il est.

La FFT:

1. donnés deux polynômes

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

   et

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

   vous pouvez calculer les coefficients du produit

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

   dans le temps de O(n log n ).

2. Donc, étant donné deux vecteurs (a_0, ..., a_n) et (b_0, ..., b_n) nous pouvons calculer   le v_i = \sum j = 0 ^ k ( a_j b_{k-j}) vecteur dans le temps de O(n log n) (en intégrant les vecteurs de zéros.)

3. Compte tenu de ce qui précède, nous devrions être en mesure de calculer le produit scalaire de A =(a_0, ..., a_n) et B =(b_0, ..., b_n) qui est A.B = \sum_j=0 ^ n a_j b_j dans le temps de O(n log n) par prétraiter l'un des vecteurs dire B à B' = (b_n, b_{n-1}, ..., b_1, b_0) puis calculer la convolution comme dans 2. O(n log n) temps.

Si le raisonnement ci-dessus est correct, cela signifie que nous pouvons mettre en œuvre matrice de deux matrices de multiplication de nxn dans le temps de O(n^2 log n ) en calculant le produit scalaire en temps O(n log n) temps de O(n).

Cependant, la meilleure exécution pour la multiplication de la matrice que nous savons est sur O(n^2.4) si cela semble peu probable pour être vrai, ce qui signifie probablement des étapes 1,2, ou 3 est incorrect.

Answer 1

Il y a des entrées n^2 dans le produit, non n et donc cet algorithme serait O(n^2 * n * log n) = O(n^3 log n).

Et le meilleur algorithme pour calculer les produits de point est O(n), pas O(n log n). Voilà pourquoi l'algorithme naïf pour la multiplication de la matrice est O(n^3). (Il est des produits de point n^2 qui peut être fait dans le temps de O(n)).

Answer 2

Je me demande pourquoi il est une réalisation qui à l'étape 3, vous pouvez calculer le produit scalaire dans O (n log n) comme il est bien connu que le produit scalaire peut être calculé en O (n)? étape également 2 ressemble à un temps linéaire au lieu de O (n log n) pas?

En outre la conclusion à propos de O (n ^ 2 log n) ne suit pas logiquement. Vous ne pouvez pas prendre le produit scalaire O (n) fois résultant dans la matrice AB --- pour autant que je sais que vous devez prendre des produits de point O (n ^ 2), conduisant à (selon votre analyse) O (n ^ 3 log n) qui est inférieur à la norme O (n ^ 3). Ceci est à cause de votre O étrange (n log n) résultat produit scalaire.