Fibonacci Number

Q: Jaka jest złożoność czasowa rekurencyjnej funkcji Fibonacciego?

Naiwna rekurencja wykonuje 2 × F(n+1) - 1 wywołań — ich liczba rośnie jak 1.618^n i jest zwykle zapisywana jako O(2^n) . Dla n = 45 to około 3.7 × 10^9 wywołań. Zapisanie każdego wyniku tylko raz, w tablicy lub w dwóch zmiennych, zmniejsza złożoność do O(n) .

Q: Jak rozwiązać problem ciągu Fibonacciego za pomocą programowania dynamicznego?

Zacznij od rekurencji F(n) = F(n-1) + F(n-2) i obliczaj wartości w rosnącej kolejności n , zapisując każdą z nich. Możesz wypełniać tabelę od dołu do góry albo zachować funkcję rekurencyjną i buforować jej wyniki — nazywa się to memoizacją. Tak czy inaczej każda wartość jest obliczana raz, więc łączna praca wynosi O(n) .

Q: Czy liczbę Fibonacciego można obliczyć przy użyciu O(1) pamięci?

Tak. Każda liczba zależy tylko od dwóch poprzednich, więc wystarczą dwie zmienne. Zachowuj dwie ostatnie wartości i przesuwaj je do przodu na każdym kroku. To daje czas O(n) i dodatkową przestrzeń O(1) .

Q: Czy istnieje szybszy sposób niż O(n)?

Tak. Macierz [[1, 1], [1, 0]] podniesiona do potęgi n ma wartość F(n) w prawym górnym rogu, a wielokrotne potęgowanie przez podnoszenie do kwadratu oblicza tę potęgę w O(log n) mnożeniach macierzy. Istnieje również wzór jawny wykorzystujący potęgi złotej proporcji, ale działa on na liczbach zmiennoprzecinkowych i traci precyzję, gdy n rośnie, dlatego preferowane są metody całkowitoliczbowe.

PoczątkującyProgramowanie dynamiczne Rekurencja

+10

Liczby Fibonacciego zaczynają się od F(0) = 0 i F(1) = 1, a każda kolejna liczba jest sumą dwóch poprzednich: F(n) = F(n-1) + F(n-2). Ciąg zaczyna się tak: 0, 1, 1, 2, 3, 5, 8, 13. Twoja funkcja otrzymuje n i zwraca F(n).

Funkcja

fib(n: integer) → integer

ninteger: pozycja w ciągu Fibonacciego, licząc od 0
Zwracainteger: liczba F(n) ciągu Fibonacciego

Ograniczenia

0 ≤ n ≤ 45
Odpowiedź mieści się w 32-bitowej liczbie całkowitej ze znakiem: F(45) = 1134903170.

Przykłady

Wejście: n = 4
Wyjście: 3
Wyjaśnienie: Policz w górę od początku: F(2) = 1 + 0 = 1, F(3) = 1 + 1 = 2 i F(4) = 2 + 1 = 3.

Wejście: n = 10
Wyjście: 55
Wyjaśnienie: Ciąg o indeksie 0 zaczyna się od 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. Liczba o indeksie 10 to 34 + 21 = 55.

+13 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy potrafisz obliczyć F(n) w czasie O(log n)?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Definicja jest już funkcją rekurencyjną, a zapisanie jej w tej postaci daje poprawną odpowiedź. Pułapką jest czas działania: dwa wywołania rekurencyjne powtarzają swoją pracę, a liczba wywołań rośnie wykładniczo wraz z n. Programowanie dynamiczne rozwiązuje ten problem, obliczając każdą liczbę Fibonacciego tylko raz, od dołu do góry. Ostatni krok zachowuje tylko dwie liczby potrzebne do obliczenia kolejnej.

Rekurencja wprost z definicji

Poprawne, ale nie kończy się na największych testach

Intuicja

Przetłumacz definicję słowo w słowo. fib(0) to 0, fib(1) to 1, a każda większa wartość zwraca fib(n-1) + fib(n-2). Każdy łańcuch wywołań kończy się jednym z dwóch przypadków bazowych, więc wynik jest poprawny.

Policzmy teraz wywołania. fib(5) wywołuje fib(4) i fib(3), ale fib(4) ponownie wywołuje fib(3). Ostatecznie fib(3) uruchamia się dwa razy, fib(2) trzy razy, a fib(1) pięć razy, zaś fib(5) wykonuje łącznie 15 wywołań. Te same wartości są obliczane wielokrotnie.

Liczba wywołań odpowiada samym liczbom Fibonacciego: obliczenie F(n) wykonuje 2 × F(n+1) - 1 wywołań. Dla n = 45 to około 3.7 × 10^9 wywołań, zdecydowanie za dużo, by zmieścić się w limicie czasu. Granicę tę zwykle zapisuje się jako O(2^n); dokładne tempo wzrostu to około 1.618^n. Rekurencja ma głębokość tylko n poziomów, więc stos potrzebuje O(n) miejsca.

Algorytm

Jeśli n wynosi 0 lub 1, zwróć n.
W przeciwnym razie wywołaj funkcję dla n-1 i n-2.
Zwróć sumę dwóch wyników.

def fib(n):
    if n < 2:
        return n  # F(0) = 0, F(1) = 1
    return fib(n - 1) + fib(n - 2)

Wypełnij tabelę od dołu do góry

Intuicja

Rekurencja jest powolna tylko dlatego, że zapomina. Jeśli zapiszesz każdą liczbę Fibonacciego przy pierwszym obliczeniu, każda będzie wymagała jednego dodawania. Utwórz tabelę f z miejscami dla indeksów od 0 do n, ustaw f[0] = 0 i f[1] = 1, a pozostałe wartości obliczaj od lewej do prawej według wzoru f[i] = f[i-1] + f[i-2].

Kolejność od lewej do prawej sprawia, że to działa: gdy dojdziesz do f[i], obie potrzebne liczby są już w tabeli. Dla n = 10 tabela wypełnia się wartościami 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, a odpowiedzią jest ostatnia wartość.

To programowanie dynamiczne w najprostszej postaci: zależność rekurencyjna oraz tabela wyników dla mniejszych przypadków. Wykonujemy n-1 dodawań, czas działania wynosi O(n), a tabela przechowuje n + 1 liczb, więc zajętość pamięci wynosi O(n). Dla n = 45 potrzeba teraz 44 dodawań zamiast miliardów wywołań.

Algorytm

Jeśli n wynosi 0 lub 1, zwróć n.
Utwórz tablicę z n + 1 liczbami, gdzie f[0] = 0 i f[1] = 1.
Dla i od 2 do n ustaw f[i] = f[i-1] + f[i-2].
Zwróć f[n].

def fib(n):
    if n < 2:
        return n
    f = [0] * (n + 1)  # f[i] will hold F(i)
    f[1] = 1
    for i in range(2, n + 1):
        f[i] = f[i - 1] + f[i - 2]
    return f[n]

Zachowaj tylko dwie ostatnie liczby

Intuicja

Przyjrzyj się temu, co odczytuje pętla korzystająca z tablicy. Aby wypełnić f[i], potrzebuje ona f[i-1] i f[i-2], a niczego starszego, więc wszystkie wcześniejsze miejsca są zbędne. Zamiast tablicy użyj dwóch zmiennych: prev przechowuje liczbę sprzed dwóch kroków, a curr liczbę sprzed jednego kroku.

Zacznij od prev = 0 i curr = 1, czyli F(0) i F(1). W każdym kroku oblicz next = prev + curr, a następnie przesuń parę do przodu: prev przyjmuje poprzednią wartość curr, a curr przyjmuje next. Dla n = 4 para zmienia się z (0, 1) na (1, 1), (1, 2) i (2, 3), a curr = 3 jest odpowiedzią.

Wykonujemy tyle samo, czyli n-1 dodawań. Złożoność czasowa wynosi O(n), a w pamięci przechowujemy trzy liczby całkowite, więc złożoność pamięciowa to O(1). Kolejność aktualizacji ma znaczenie: jeśli nadpiszesz prev przed dodaniem jego wartości, suma będzie używać niewłaściwej wartości.

Algorytm

Jeśli n wynosi 0 lub 1, zwróć n.
Ustaw prev = 0 i curr = 1.
Powtórz n-1 razy: oblicz next = prev + curr, a następnie ustaw prev = curr i curr = next.
Zwróć curr.

def fib(n):
    if n < 2:
        return n
    prev, curr = 0, 1  # F(0) and F(1)
    for _ in range(n - 1):
        prev, curr = curr, prev + curr
    return curr

Pułapki i przypadki brzegowe

Ciąg Fibonacciego to klasyczny pierwszy problem programowania dynamicznego, a większość błędów wynika z rekurencji lub z dwóch pierwszych wartości.

Oddanie naiwnej rekurencji. Przechodzi małe testy, a potem wymaga miliardów wywołań dla n = 45. Zapisuj wyniki w tablicy lub w dwóch zmiennych.
Błędne ustalenie początku. Tutaj F(0) = 0 i F(1) = 1, więc F(2) = 1 i F(10) = 55. Rozpoczęcie ciągu od 1, 1 przesuwa każdą odpowiedź o jeden indeks.
Utworzenie tablicy bez sprawdzenia małych wartości n. Dla n = 0 tablica o rozmiarze n + 1 = 1 nie ma miejsca na f[1], a zapisanie tej wartości wykracza poza jej zakres. Zwróć od razu n, gdy n < 2.
Aktualizowanie pary w niewłaściwej kolejności. prev = curr, a następnie curr = prev + curr dodaje nową wartość prev i podwaja curr. Najpierw oblicz sumę w next albo użyj jednoczesnego przypisania, jeśli dany język je obsługuje.
Wykonanie o jeden krok za dużo. Pętla, która oblicza również F(n+1), osiąga przy limicie F(46) = 1836311903, co mieści się w 32 bitach wyłącznie przez szczęśliwy zbieg okoliczności. F(47) już się nie mieści.

Najczęstsze pytania4

Jaka jest złożoność czasowa rekurencyjnej funkcji Fibonacciego?

Naiwna rekurencja wykonuje 2 × F(n+1) - 1 wywołań — ich liczba rośnie jak 1.618^n i jest zwykle zapisywana jako O(2^n). Dla n = 45 to około 3.7 × 10^9 wywołań. Zapisanie każdego wyniku tylko raz, w tablicy lub w dwóch zmiennych, zmniejsza złożoność do O(n).

Jak rozwiązać problem ciągu Fibonacciego za pomocą programowania dynamicznego?

Zacznij od rekurencji F(n) = F(n-1) + F(n-2) i obliczaj wartości w rosnącej kolejności n, zapisując każdą z nich. Możesz wypełniać tabelę od dołu do góry albo zachować funkcję rekurencyjną i buforować jej wyniki — nazywa się to memoizacją. Tak czy inaczej każda wartość jest obliczana raz, więc łączna praca wynosi O(n).

Czy liczbę Fibonacciego można obliczyć przy użyciu O(1) pamięci?

Tak. Każda liczba zależy tylko od dwóch poprzednich, więc wystarczą dwie zmienne. Zachowuj dwie ostatnie wartości i przesuwaj je do przodu na każdym kroku. To daje czas O(n) i dodatkową przestrzeń O(1).

Czy istnieje szybszy sposób niż O(n)?

Tak. Macierz [[1, 1], [1, 0]] podniesiona do potęgi n ma wartość F(n) w prawym górnym rogu, a wielokrotne potęgowanie przez podnoszenie do kwadratu oblicza tę potęgę w O(log n) mnożeniach macierzy. Istnieje również wzór jawny wykorzystujący potęgi złotej proporcji, ale działa on na liczbach zmiennoprzecinkowych i traci precyzję, gdy n rośnie, dlatego preferowane są metody całkowitoliczbowe.