Ich habe folgende Übung erhalten:
Gegebenes Polynom P und eine reelle Sequenz x 1 , ..., x n , finde die Datenstruktur D , die Ausdrücke der Form S (i, j) = P (0) x i + 1 + ... + P (j - i - 1) x j - 1 in konstanter Zeit mit einer Vorverarbeitung auf x 1 , ..., x n .
Ich habe versucht, es seit einiger Zeit zu lösen und hatte nicht viel Erfolg. Eine offensichtliche Lösung erfordert O (n 2 ) Vorverarbeitungszeit: für jedes j in 1 ... n , Ich kann berechnen P (j) = a 0 + ja 1 + j 2 <2> ... + j m a m in O (mn) Zeit. Dann kann ich Präfix-Summen für jedes S (i, j) berechnen, wobei j & gt; i in O (n) Zeit für jedes einzelne i , also in O (n 2 ) em> Zeit insgesamt. (Ich nehme nur reguläre Präfixsummen für jedes mögliche i .) Ich würde (asymptotisch) gerne schneller gehen, wenn möglich.
Das Problem scheint zu sein, dass die Berechnung von S (i, j) keine nützliche Information über S (i + 1, j) liefert. Schau: S (i, j) = P (0) x1 + P (1) x2 + ... , aber < em> S (i + 1, j) = P (0) x2 + P (1) x3 . Sehen? Die P sind nach rechts gerückt. Wenn es eine Möglichkeit gäbe, S (i + 1, j) aus S (i, j) zu berechnen, glaube ich, dass ich in O (mn) fortfahren könnte. Zeit.
Ich habe es versucht:
Berechnen Sie (normale) Präfixsummen für x 1 , ..., x n und Manipulieren der Ausdrücke, so dass die reguläre Präfixsumme verwendet werden könnte, um S (i, j) ohne Erfolg zu berechnen.
Schreiben Sie die explizite Formel für S (i, j) und gruppieren Sie die Terme nach Polynomkoeffizienten ( a i s) ) statt durch x i . Das Problem bleibt gleich.
Wenn du schneller kannst, gib mir bitte einen Hinweis, wie es weitergeht. Bitte geben Sie keine expliziten Lösungen , ich würde es gerne selbst herausfinden.
P.S .: Es gibt tatsächlich einen Hinweis, um dies zu lösen: "Generiere Präfix-Summen."
Sie können dies mit O(nm+m^2) preprocessing und memory und O(m) query time erreichen. Wenn Ihr m begrenzt ist, ist das im Grunde die Laufzeit, nach der Sie gefragt haben.
Da Sie gebeten haben, keine zu direkten Hinweise zu geben, zeige ich Ihnen nur, wie Sie Ihre Aufgabe lösen könnten, wenn Sie das einfache Polynom P(x) = x verwenden.
Definieren (und vorberechnen in% O(nm) :
Wir haben dann:
%Vor%Für konstante Zeitabfragen.
Mit ein bisschen Summenmanipulation nimmt die Verallgemeinerung des obigen% pro Zeit für allgemeine Polynome. Mit einer zusätzlichen O(m^2) Vorverarbeitung können Sie jedoch auf O(nm+m^2) Abfragezeit zugreifen. Ich vermute, das ist optimal für die Speichernutzung linear in O(m) .
Tags und Links algorithm