Wie man die Tribonacci-Zahl für sehr große n (etwa 10 ^ 14) in der besten Komplexität berechnet. Tribonacci-Nummern sind als F(n)=F(n-1)+F(n-2)+F(n-3) mit F0=1, F1=2, F2=4 definiert.
Oder Wiederholung definiert als
F(n)=aF(n-1)+bF(n-2)+cF(n-3) mit F0=1, F1=2, F2=4 .
Ich möchte den n-ten Ausdruck in log (n) berechnen, genau wie die n-te Fibonacci-Zahl.
Wie kann ich die Basismatrix zur Verwendung der Matrixexponentiation zur Berechnung der n-ten erzeugen? Begriff?
Früher habe ich versucht, es mit DP zu implementieren, aber da wir Arrays dieser Größe nicht verwenden können, funktioniert es nicht gut. In ähnlicher Weise funktionierte die Rekursion hier wegen des Stack-Überlaufs für sehr große Zahlen in der Größenordnung von 10 ^ 14 nicht.
Die beste asymptotische Komplexität für Tribonacci-Zahlen verwendet eine Matrix-Potenzierungsmethode wie die eine für Fibonacci Zahlen . Genauer gesagt, das sind ganzzahlige O (log n) -Operationen und nicht O (n) (wie die dynamische Programmiermethode) oder O (3
Die interessierende Matrix ist
%Vor% und die n Tribonacci-Nummer befindet sich in der oberen linken Ecke von M
(für F(n+3) = a F(n+2) + b F(n+1) + c F(n) ist die Matrix:
und das Ergebnis ist {Fn + 2, Fn + 1, Fn} = Mn sup> {F <2>, F1, F0 <}, auch siehe hier .)
Eine dynamische Programmierlösung benötigt kein 10 ^ 14 Elemente-Array. Es erfordert nur 3 .
Beachten Sie, dass jeder Schritt nur die vorherigen drei Elemente verwendet. Für F(1000) benötigen Sie also wirklich nicht F(5) .
Sie können Elemente, die nicht mehr benötigt werden, einfach überschreiben und sie als neue Nummer betrachten.
Der Operator % ist Ihr Freund für diesen Zweck.