Când munca se dublează
O(2ⁿ) înseamnă timp exponențial: un singur element în plus la intrare dublează munca. Aceasta este clasa de creștere la care algoritmii nu mai pot fi folosiți — nu doar pentru date de intrare uriașe, ci deja pentru unele medii.
Munca exponențială apare de obicei din recursivitatea care se ramifică: o funcție care se apelează pe ea însăși de două ori, iar fiecare dintre aceste apeluri se apelează din nou de două ori. Apelurile formează un arbore care se dublează la fiecare nivel.
Fibonacci recursiv
Șirul lui Fibonacci începe cu 0, 1, iar fiecare număr următor este suma celor două dinaintea lui: 0, 1, 1, 2, 3, 5, 8, 13, …
Definiția se transformă direct într-o funcție recursivă: fib(n) returnează fib(n-1) + fib(n-2). Este scurtă și corectă — dar exponențială, pentru că fiecare apel mai generează încă două, iar aceleași valori sunt calculate iar și iar. Doar fib(2) este recalculat de mii de ori într-un apel mai mare.
Fibonacci cu recursivitate
Un contor global numără fiecare apel. Calculul fib(10) = 55 necesită 177 de apeluri — pentru un singur număr mic. Arborele de apeluri se dublează la fiecare nivel.
Ieșire: program Python complet
calls = 0
def fib(n):
global calls
calls += 1
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print("fib(10) =", fib(10))
print("apeluri de funcție:", calls)
De ce explodează
Urmăriți numărul de apeluri pe măsură ce n crește cu câte 5. El nu crește cu pași egali — se înmulțește. Fiecare +1 la n înseamnă aproximativ ×1,6 la apeluri; fiecare +5, mai mult de ×10.
La n = 50 numărul ar depăși 40 de miliarde de apeluri. Aceasta este capcana exponențială: codul pare inofensiv, iar testele mici se termină instantaneu.
Numărați apelurile pe măsură ce n crește
De la fib(5) la fib(25) intrarea crește de 5 ori — numărul de apeluri crește de peste 16 000 de ori, de la 15 la 242785.
Ieșire: program Python complet
calls = 0
def fib(n):
global calls
calls += 1
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
for n in [5, 10, 15, 20, 25]:
calls = 0
fib(n)
print(f"fib({n:2d}) -> {calls:7d} apeluri")
Soluția: o buclă
Problema nu este Fibonacci — ci calcularea acelorași valori din nou și din nou. O buclă care urcă pornind de la 0 și 1, păstrând doar ultimele două valori, calculează fiecare număr exact o dată.
Asta înseamnă timp O(n) și spațiu O(1): 24 de pași în loc de 242785 de apeluri pentru fib(25). Același răspuns, o altă clasă de creștere — exact pentru asta există analiza algoritmilor.
Fibonacci cu o buclă
Două variabile urcă de-a lungul șirului; fiecare pas calculează un număr nou. fib(25) = 75025 în 24 de pași — versiunea recursivă avea nevoie de 242785 de apeluri pentru același răspuns.
Ieșire: program Python complet
n = 25
steps = 0
a, b = 0, 1
for i in range(2, n + 1):
a, b = b, a + b
steps += 1
print("fib(25) =", b)
print("pașii buclei:", steps)