Klärung FFT
-
19-09-2019 - |
Frage
Ich weiß, es ist etwas falsch mit der folgenden Argumentation, aber ich bin mir nicht sicher, was es ist.
Die FFT:
-
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. -
So zwei Vektoren
(a_0, ..., a_n)
gegeben und(b_0, ..., b_n)
wir berechnen können, der Vektorv_i = \sum j = 0 ^ k ( a_j b_{k-j})
inO(n log n)
Zeit (durch die Vektoren in Nullen einzubetten.) -
Das führte zu dem, sollten wir in der Lage sein, das Skalarprodukt
A =(a_0, ..., a_n)
undB =(b_0, ..., b_n)
zu berechnen, dieA.B = \sum_j=0 ^ n a_j b_j
inO(n log n)
Zeit ist von einem der Vektoren Vorverarbeitung sagenB
B' = (b_n, b_{n-1}, ..., b_1, b_0)
werden dann die Faltung Berechnung wie in 2 inO(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.
Lösung
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).
Andere Tipps
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.