xiikzodz pisze:W ogólności wzór Bineta jest niefortunny, bo dla dużych \(\displaystyle{ n}\) zaokrąglenia mogą przekroczyć \(\displaystyle{ 1}\).
Możesz skorzystać z tożsamości:
\(\displaystyle{ F_n=F_{(n+1)/2}^2+F_{(n-1)/2}^2}\)
dla nieparzystych \(\displaystyle{ n}\)
\(\displaystyle{ F_n=F_{n/2+1}^2-F_{n/2-1}^2}\)
dla parzystych \(\displaystyle{ n}\).
Daje to żądaną złożoność obliczeniową.
Edt: dzieki za uwage, poprawione.
no właśnie to nie jest wcale takie oczywiste, że to da odpowiednią złożoność, bo implementując to tak po prostu narażamy się na wielokrotne obliczanie tych samych wartości. Z ciekawości chciałbym zobaczyć ile razy wywoła się
\(\displaystyle{ F(1)}\) jak odpalę
\(\displaystyle{ F(100000000)}\).
Edit: teraz widze, ze to w ogóle ani troche nie daje złożoności
\(\displaystyle{ O(\lg n)}\)
Równanie rekurencyjne na koszt algorytmu ma postac:
\(\displaystyle{ T(n)=2*T(n/2)+O(1)}\), co daje tylko
\(\displaystyle{ O(n)}\). Ale i tak napiszę poniżej jak to naprawić, żeby przeszlo z czasem
\(\displaystyle{ 0.00}\)
Zazwyczaj w takich przypadkach stosuje się programowanie dynamiczne, czyli "liczymy od dołu". Ale tutaj niestety nie możemy sobie na to pozwolić, bo takich dużych tablic nie uda się pomieścić. Drugi sposób to "spamiętywanie", czyli za każdym razem gdy obliczę
\(\displaystyle{ F(n)}\) to zapamiętuję sobie wynik tych obliczeń, dzięki czemu nigdy nie wykonam tej samej pracy dwa razy. Tutaj kłopot jest znowu ten sam, bo jak zapamiętać
\(\displaystyle{ F(n)}\) dla wielkich
\(\displaystyle{ n}\) (tablica odpada). Rozwiązanie, które można zastosować to skorzystać z mapy (struktura map z STLa), wygląda to jak tablica, ale można używać dowolnie dużych kluczy (od środka to drzewo czerwono-czarne).
Nie wiem czy już udało Ci się odnaleźć błąd w tamtym rozwiązaniu, ale ono jest generalnie dobre, sam z ciekawości je wczoraj zaimplementowałem (jeśli chcesz zobaczyć kod to pisz). Ale akurat nie uważam go za najlepsze, mimo że bardzo sprytne. Jest sposób bardzo ogólny i dużo sprytniejszy .
xiikzodz zna ten sposób, ale być może sama nie jest tego świadoma. "Niestety" sposób ten wymaga znajomości operacji mnożenia macierzy. Zauważmy taką oto zależność:
jeśli
\(\displaystyle{ f_n}\) to n-ta liczba Fibonacciego, to zachodzi:
\(\displaystyle{ \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\cdot \begin{bmatrix} f_{n+1} \\ f_n \end{bmatrix}=\begin{bmatrix} f_{n+1}+f_n \\ f_{n+1} \end{bmatrix}=
\begin{bmatrix} f_{n+2} \\ f_{n+1} \end{bmatrix}}\)
To nie wygląda jeszcze na nic fajnego. Ale dzieki temu przez indukcje mozna pokazac:
\(\displaystyle{ \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n\cdot \begin{bmatrix} f_{1} \\ f_0 \end{bmatrix}=\begin{bmatrix} f_{n+1}\\ f_{n} \end{bmatrix}}\)
Zatem sprowadziliśmy liczenie liczb fib. do potęgowania (macierzy). Co to znaczy? To znaczy, że możemy je obliczać w
\(\displaystyle{ O(\lg n)}\). Bo tyle nas kosztuje potęgowanie. Algorytm szybkiego potęgowania wygląda tutaj dokładnie tak samo jak dla liczb. Ogólnie potęgowanie w każdej półgrupie można wykonywać w takim czasie, wystarczy nam tylko łączność mnożenia.