Dies kann in O(n log n) Zeit für beliebige P und Q von Grad n durchgeführt werden. Genauer gesagt kann dies in M(n) erfolgen, wobei M(n) die Komplexität der Polynom-Multiplikation ist, die selbst in O(n log n) gemacht werden kann.
Erstens, die ersten n Begriffe einer Reihenentwicklung kann einfach als ein Polynom Grad n-1 angesehen werden.
Angenommen, Sie interessieren sich für die ersten n Begriffe der Serie Erweiterung von P(x)/Q(x). Es existiert ein Algorithmus, der das Inverse von Q in M(n) Zeit wie oben definiert berechnen wird.
Inverse T(x) von Q(x) erfüllt T(x) * Q(x) = 1 + O(x^N). I.e. T(x) * Q(x) ist genau 1 plus einige Fehler Begriff, deren Coficients alle kommen nach den ersten n Begriffe, die wir interessieren, so können wir sie einfach fallen lassen.
Jetzt P(x)/Q(x) ist einfach P(x) * T(x) das ist nur eine weitere Polynom Multiplikation.
Sie können eine Implementierung finden, die das zuvor erwähnte Inverse in meiner Open-Source-Bibliothek Altruct berechnet. Siehe die Datei series.h. Angenommen, Sie haben bereits eine Methode, die das Produkt von zwei Polyinomen berechnet, ist der Code, der die Umkehrung berechnet, etwa 10 Zeilen lang (eine Variante von Divide-and-Conquer). Der tatsächliche Algorithmus ist wie folgt: Angenommen Q(x) = 1 + a1*x + a2*x^2 + .... Wenn a0 nicht 1 ist, können Sie einfach Q(x) und später dessen inverse mit a0 teilen. Nehmen Sie an, dass Sie bei jedem Schritt L Begriffe der umgekehrten haben, so dass Q(x) * T_L(x) = 1 + x^L * E_L(x) für einen Fehler E_L(x). Anfangs T_1(X) = 1. Wenn Sie dies oben einstecken, erhalten Sie Q(x) * T_1(x) = Q(x) = 1 + x^1 * E_1(x) für einige E_1(x), was bedeutet, dass dies für L=1 gilt. Lassen Sie uns jetzt bei jedem Schritt L verdoppeln. Sie können E_L(x) aus dem vorherigen Schritt als E_L(x) = (Q(x) * T_L(x) - 1)/x^L erhalten, oder implementieren Sie einfach die ersten L Koeffizienten des Produkts. Sie können dann T_2L(x) aus dem vorherigen Schritt als T_2L(x) = T_L(x) - x^L * E_L(x) * T_L(x) berechnen. Der Fehler wird E_2L(x) = - E_L(x)^2 sein.Prüfen wir nun, ob der Induktionsschritt gilt.
Q(x) * T_2L(x)
= Q(x) * (T_L(x) - x^L * E_L(x) * T_L(x))
= Q(x) * T_L(x) * (1 - x^L * E_L(x))
= (1 + x^L * E_L(x)) * (1 - x^L * E_L(x))
= 1^2 - (x^L * E_L(x))^2
= 1 + x^2L * E_2L(x)
Q.E.D.
Ich bin ziemlich sicher, dass es nicht möglich ist, Polynomdivision effizienter als Multiplikation zu berechnen, und wie Sie in der folgenden Tabelle sehen können, dieser Algorithmus nur 3-mal langsamer als eine einzige Multiplikation ist:
n mul inv factor
10^4 24 ms 80 ms 3,33x
10^5 318 ms 950 ms 2,99x
10^6 4.162 ms 12.258 ms 2,95x
10^7 101.119 ms 294.894 ms 2,92x
@ DavidEisenstat Danke, das vereinfacht die Aufgabe. Aber wie kann ich '1/Q (x)' mit langer Teilung finden? Ich dachte bei der Division finde ich nur Quotient und Rest. – Somnium
@DavidEisenstat Vielen Dank! Die Vermeidung von Trennung wird auch die Dinge beschleunigen, weil die Multiplikation * O (n * m) * ist, wobei n - Anzahl der Terme, m - Grad. Übrigens verstehe ich nicht, warum meine Antwort als zu breit markiert ist, sondern einen bestimmten Algorithmus. – Somnium
@DavidEisenstat Da gehen Sie :) Vielleicht sollten wir ein Thema über den Zustand von [Algorithmus] auf Meta starten. Es gibt definitiv einige allgemeine Entscheidungen, die getroffen werden müssen, um diese Fragen an CS –