Klärung FFT

Question

Ich weiß, es ist etwas falsch mit der folgenden Argumentation, aber ich bin mir nicht sicher, was es ist.

Die FFT:

1. gegeben zwei Polynome

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

   und

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

   Sie können die Koeffizienten des Produkts berechnen

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

   in O(n log n ) Zeit.

2. So zwei Vektoren (a_0, ..., a_n) gegeben und (b_0, ..., b_n) wir berechnen können,   der Vektor v_i = \sum j = 0 ^ k ( a_j b_{k-j}) in O(n log n) Zeit (durch die Vektoren in Nullen einzubetten.)

3. Das führte zu dem, sollten wir in der Lage sein, das Skalarprodukt A =(a_0, ..., a_n) und B =(b_0, ..., b_n) zu berechnen, die A.B = \sum_j=0 ^ n a_j b_j in O(n log n) Zeit ist von einem der Vektoren Vorverarbeitung sagen B B' = (b_n, b_{n-1}, ..., b_1, b_0) werden dann die Faltung Berechnung wie in 2 in O(n log n) Zeit.

Wenn die obige Argumentation richtig ist, dann ist das Mittel, die wir Matrixmultiplikation von zwei nxn Matrizen in O(n^2 log n ) Zeit durch Berechnung des Skalarprodukts in O(n log n) Zeit O(n) mal umsetzen können.

Allerdings ist die beste Laufzeit für die Matrixmultiplikation wir wissen, ist über O(n^2.4) so dies unwahrscheinlich scheint, um wahr zu sein, was wahrscheinlich mittels der Schritte 1,2 oder 3 ist falsch.

Answer 1

Es gibt n^2 Einträge im Produkt nicht n und so dieser Algorithmus O(n^2 * n * log n) = O(n^3 log n) sein würde.

Und der beste Algorithmus für Skalarprodukte Berechnung ist O(n), nicht O(n log n). Deshalb ist der naive Algorithmus für die Matrixmultiplikation ist O(n^3). (Es ist n^2 Punktprodukte, die in O(n) Zeit durchgeführt werden können).

Answer 2

Ich frage mich, warum es ein Erfolg ist, dass in Schritt 3 Sie das Skalarprodukt in O berechnen kann (n log n) Zeit, wie es bekannt ist, dass Punktprodukt kann in O (n) Zeit berechnet werden? Schritt 2 auch sehen aus wie die lineare Zeit statt O (n log n) Schritt?

Auch die Aussage über O (n ^ 2 log n) folgt nicht logisch. Sie können das Punktprodukt O nicht nehmen (n) mal in der AB-Matrix führt --- soweit ich weiß, Sie O nehmen (n ^ 2) dot Produkte, was zu (pro Ihrer Analyse) O (n ^ 3 log n), die schlechter als Standard-O (n ^ 3). Dies liegt daran, Ihre seltsamen O (n log n) Produkt Ergebnis dot.