Dlaczego liczby Fibonacciego są istotne w informatyce?

Liczby Fibonacciego mają bardzo ładne właściwości matematyczne, które czynią je doskonałymi w informatyce. Oto kilka:

1. Rosną wykładniczo szybko. interesującą strukturą danych, w której pojawia się szereg Fibonacciego, jest drzewo AVL, forma samobalansującego się drzewa binarnego. Intuicja stojąca za tym drzewem polega na tym, że każdy węzeł utrzymuje współczynnik równowagi tak, że wysokość lewego i prawego poddrzewa różni się co najwyżej o jeden. Z tego powodu, można myśleć o minimalnej liczbie węzłów niezbędnych do uzyskania drzewa AVL o wysokości h jest określona przez powtarzanie, które wygląda jak N (h + 2) ~= n (h) + N (h + 1), które wygląda podobnie jak szereg Fibonacciego. Jeśli opracujesz matematykę, możesz pokazać, że liczba węzłów potrzebnych do uzyskania drzewa AVL o wysokości h wynosi F (h + 2) - 1. Ponieważ seria Fibonacciego rośnie wykładniczo szybko, oznacza to, że wysokość drzewa AVL jest co najwyżej logarytmiczna w liczbie węzłów, co daje O (lg n) czas wyszukiwania znamy i kochamy zrównoważone drzewa binarne. W rzeczywistości, jeśli możesz powiązać rozmiar jakiejś struktury z liczbą Fibonacciego, prawdopodobnie otrzymasz runtime O (lg n) przy jakiejś operacji. Jest to prawdziwy powód, dla którego stosy Fibonacciego nazywane są stosami Fibonacciego - dowód, że liczba stosów po dequeue min wiąże się z ograniczeniem liczby węzłów, które możesz mieć w określonej głębokości za pomocą liczby Fibonacciego.
2. dowolną liczbę można zapisać jako sumę unikalnych Fibonacciego liczby. ta właściwość liczb Fibonacciego ma kluczowe znaczenie dla poprawienia działania wyszukiwania Fibonacciego; jeśli nie możesz dodać unikalnych liczb Fibonacciego do dowolnej możliwej liczby, wyszukiwanie to nie zadziała. Porównaj to z wieloma innymi seriami, takimi jak 3 ⁿ lub liczby katalońskie. To jest również częściowo, dlaczego wiele algorytmów, takich jak moce dwóch, myślę.
3. liczby Fibonacciego są wydajnie obliczalne. fakt, że szereg może być generowany bardzo efektywnie (można uzyskać pierwsze N terminów w O (n) lub dowolny dowolny termin w O (lg n)), wtedy wiele algorytmów, które ich używają, nie byłoby praktycznych. Generowanie liczb katalońskich jest dość skomplikowane obliczeniowo, IIRC. Ponadto, liczby Fibonacciego mają ładną właściwość, gdzie, biorąc pod uwagę dowolne dwie kolejne liczby Fibonacciego, powiedzmy F (k) I F(k + 1), Możemy łatwo obliczyć następną lub poprzednią liczbę Fibonacciego, dodając dwie wartości (F(k) + F(k + 1) = F(k + 2)) lub F (K + 1). odejmując je (F (k + 1) - F(k) = F(k-1)). Właściwość ta jest wykorzystywana w kilku algorytmach, w połączeniu z właściwością (2), do rozbijania liczb na sumę liczb Fibonacciego. Na przykład wyszukiwanie Fibonacciego wykorzystuje to do lokalizowania wartości w pamięci, podczas gdy podobny algorytm może być użyty do szybkiego i wydajnego obliczania logarytmów.
4. Są przydatne pedagogicznie. Nauczanie rekurencji jest trudne, a seria Fibonacciego jest świetnym sposobem na jej wprowadzenie. You can talk o prostej rekurencji, o memoizacji lub o dynamicznym programowaniu przy wprowadzaniu serii. Dodatkowo, zdumiewająca forma zamknięta dla liczb Fibonacciego jest często nauczana jako ćwiczenie w indukcji lub w analizie nieskończonych szeregów, a powiązane równanie macierzowe dla liczb Fibonacciego jest powszechnie wprowadzane w algebrze liniowej jako motywacja za wektory własne i wartości własne. Myślę, że jest to jeden z powodów, dla których są tak głośne w zajęcia wprowadzające.

Jestem pewien, że jest więcej powodów niż tylko to, ale jestem pewien, że niektóre z tych powodów są głównymi czynnikami. Mam nadzieję, że to pomoże!