Fibonacci - implementacje iteracyjna i rekurencyjna
1. Liczby Fibonacciego
Ciąg Fibonacciego to sekwencja liczb, gdzie każda liczba jest sumą dwóch poprzednich.
Definicja matematyczna:
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) dla n ≥ 2
Pierwszych 15 liczb Fibonacciego:
n: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
F(n): 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
Zastosowania:
- Matematyka (złoty podział: φ ≈ 1.618)
- Przyroda (spirale w muszlach, rośliny)
- Algorytmy (wyszukiwanie Fibonacciego)
- Analiza algorytmów (najgorszy przypadek dla algorytmów)
2. Rekurencja naiwna – KATASTROFA!
2.1. Implementacja
2.2. Problem: Wykładnicza złożoność!
Drzewo wywołań dla fibonacci_rek_naiwna(5):
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
/ \
fib(1) fib(0)
Obserwacje:
- fib(3) obliczane 2 razy
- fib(2) obliczane 3 razy
- fib(1) obliczane 5 razy
- fib(0) obliczane 3 razy
Liczba wywołań: 15 dla fib(5), 177 dla fib(10), 2 692 537 dla fib(20)!
2.3. Złożoność czasowa: O(2^n)
Przykładowe wyniki:
fib(10) = 55 w 0.0001s
fib(20) = 6,765 w 0.0023s
fib(30) = 832,040 w 0.2891s
fib(35) = 9,227,465 w 3.5214s ← BARDZO WOLNO!
Dla fib(40) – kilkadziesiąt sekund! Dla fib(50) – kilka dni!
3. Rekurencja z memoizacją – ZNACZNIE LEPIEJ!
3.1. Implementacja z dict
3.2. Implementacja z dekoratorem @lru_cache
3.3. Złożoność czasowa: O(n)
Porównanie: - Naiwna fib(35): 3.5s - Memo fib(35): 0.00001s - Różnica: 350,000x szybciej!
3.4. Jak działa memoizacja?
fib_memo(5):
fib(5) → brak w cache, oblicz
fib(4) → brak, oblicz
fib(3) → brak, oblicz
fib(2) → brak, oblicz
fib(1) → 1 (bazowy)
fib(0) → 0 (bazowy)
zapisz fib(2) = 1
fib(1) → 1 (bazowy)
zapisz fib(3) = 2
fib(2) → JEST W CACHE = 1 ← Nie obliczamy ponownie!
zapisz fib(4) = 3
fib(3) → JEST W CACHE = 2 ← Nie obliczamy ponownie!
zapisz fib(5) = 5
Każda wartość obliczana tylko raz!
4. Iteracja – NAJLEPSZE ROZWIĄZANIE!
4.1. Implementacja z dwiema zmiennymi
Jak to działa (n=7):
n=2: a=0, b=1 → a, b = 1, 0+1=1
n=3: a=1, b=1 → a, b = 1, 1+1=2
n=4: a=1, b=2 → a, b = 2, 1+2=3
n=5: a=2, b=3 → a, b = 3, 2+3=5
n=6: a=3, b=5 → a, b = 5, 3+5=8
n=7: a=5, b=8 → a, b = 8, 5+8=13
return 13
4.2. Złożoność:
- Czasowa: O(n)
- Pamięciowa: O(1) ← NAJLEPSZE!
4.3. Benchmark – porównanie wszystkich metod
Przykładowe wyniki dla fib(30):
Naiwna rekurencja : 832,040 w 0.289123s
Memo (dict) : 832,040 w 0.000012s
LRU cache : 832,040 w 0.000009s
Iteracja : 832,040 w 0.000004s ← NAJSZYBSZA!
5. Wszystkie implementacje obok siebie
6. Fibonacci z generatorem
Gdy potrzebujesz wielu wartości Fibonacciego:
7. Porównanie złożoności
| Metoda | Czas | Pamięć | Zalety | Wady |
|---|---|---|---|---|
| Naiwna rekurencja | O(2^n) | O(n) | Prosta | BARDZO WOLNA |
| Memoizacja (dict) | O(n) | O(n) | Szybka, elastyczna | Wymaga pamięci |
| @lru_cache | O(n) | O(n) | Szybka, wygodna | Wymaga pamięci |
| Iteracja | O(n) | O(1) | Najszybsza, najmniej pamięci | Mniej elegancka |
| Rekurencja ogonowa | O(n) | O(n)* | Elegancka | Brak korzyści w Pythonie |
| Formula Bineta | O(1) | O(1) | Bardzo szybka | Problemy z precyzją |
*Python nie optymalizuje tail recursion
8. Formula Bineta – O(1)
Bezpośrednia formula matematyczna:
Problem: Błędy zaokrągleń dla dużych n!
9. Fibonacci macierzowy – O(log n)
Można obliczyć Fibonacciego w O(log n) używając potęgowania macierzy:
Złożoność: O(log n) – używa szybkiego potęgowania!
10. Praktyczne zastosowania
10.1. Suma pierwszych n liczb Fibonacciego
10.2. Czy liczba jest Fibonaccim?
10.3. Złoty podział (φ)
11. Kiedy używać której implementacji?
Naiwna rekurencja
❌ NIGDY – tylko do celów edukacyjnych
Memoizacja
✅ Gdy potrzebujesz jednej wartości dużego Fibonacciego ✅ Gdy masz dostęp do cache między wywołaniami
Iteracja
✅ DOMYŚLNY WYBÓR – szybka, mało pamięci ✅ Gdy liczysz wiele małych wartości ✅ Produkcja
Generator
✅ Gdy potrzebujesz wielu kolejnych wartości ✅ Nieskończony strumień danych
Formula Bineta
✅ Gdy n jest małe (< 70) ✅ Gdy potrzebujesz przybliżenia ❌ Unikaj dla dużych n (błędy zaokrągleń)
12. Podsumowanie
Fibonacci – różne podejścia:
| Implementacja | Czas | Pamięć | Najlepsze dla |
|---|---|---|---|
| Naiwna rek | O(2^n) | O(n) | ❌ Edukacja tylko |
| Memoizacja | O(n) | O(n) | Pojedyncze duże n |
| Iteracja | O(n) | O(1) | ✅ Produkcja |
| Generator | O(n) | O(1) | Wiele kolejnych wartości |
| Binet | O(1) | O(1) | Małe n, przybliżenia |
| Macierzowa | O(log n) | O(1) | Bardzo duże n |
Kluczowe wnioski:
- Naiwna rekurencja = katastrofa (O(2^n))
- Memoizacja = ratuje rekurencję (O(2^n) → O(n))
- Iteracja = najlepsza w Pythonie (O(n) czas, O(1) pamięć)
- Generator = wygodny dla wielu wartości
- Python nie optymalizuje rekurencji ogonowej!
Złota zasada:
W Pythonie dla Fibonacciego: użyj iteracji lub memoizacji
Co dalej warto poznać:
- Programowanie dynamiczne
- Szybkie potęgowanie macierzy
- Inne ciągi rekurencyjne (Tribonacci, Lucas)
- Aplikacje złotego podziału