Când munca se dublează
O(2ⁿ) înseamnă timp exponențial: un singur element suplimentar la intrare dublează munca. Aceasta este clasa de creștere în care algoritmii încetează să mai fie utilizabili — nu pentru intrări uriașe, ci deja pentru unele medii.
Munca exponențială vine de obicei dintr-o recursivitate care se ramifică: o funcție care se apelează pe sine de două ori, iar fiecare dintre acele 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 traduce direct într-o funcție recursivă: fib(n) returnează fib(n - 1) + fib(n - 2). Este scurtă și corectă — și exponențială, pentru că fiecare apel naște alte 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 din afara funcției numără fiecare apel. Calcularea lui fib(10) = 55 ia 177 de apeluri — pentru un singur număr mic. Arborele de apeluri se dublează la fiecare nivel.
Ieșire: program TypeScript și rezultatul capturat
let calls = 0
function fib(n: number): number {
calls++
if (n < 2) {
return n
}
return fib(n - 1) + fib(n - 2)
}
console.log("fib(10) =", fib(10))
console.log("apeluri de funcție:", calls)
De ce explodează
Urmărește numărul de apeluri pe măsură ce n crește din 5 în 5. Nu crește cu pași — se înmulțește. Fiecare +1 la n înseamnă aproximativ ×1,6 la apeluri; fiecare +5 înseamnă mai mult de ×10.
La n = 50 numărul ar depăși 40 de miliarde de apeluri. Aceasta este capcana exponențială: codul pare nevinovat, iar testele mici se termină instantaneu.
Numărăm 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 242.785.
Ieșire: program TypeScript și rezultatul capturat
let calls = 0
function fib(n: number): number {
calls++
if (n < 2) {
return n
}
return fib(n - 1) + fib(n - 2)
}
for (const n of [5, 10, 15, 20, 25]) {
calls = 0
fib(n)
const label = String(n).padStart(2)
console.log(`fib(${label}) -> ${String(calls).padStart(7)} apeluri`)
}
Soluția: o buclă
Problema nu este Fibonacci — ci faptul că aceleași valori sunt calculate la nesfârșit. O buclă care urcă de la 0 și 1, păstrând doar ultimele două valori, calculează fiecare număr exact o dată.
Acesta este timp O(n) și spațiu O(1): 24 de pași în loc de 242.785 de apeluri pentru fib(25). Același răspuns, o altă clasă de creștere — exact la asta servește analiza algoritmilor.
Fibonacci cu o buclă
Două variabile urcă pe șir; fiecare rundă calculează un număr nou. fib(25) = 75025 în 24 de pași — versiunea recursivă avea nevoie de 242.785 de apeluri pentru același răspuns.
Ieșire: program TypeScript și rezultatul capturat
const n = 25
let steps = 0
// Păstrăm doar ultimele două valori și urcăm pe șir.
let a = 0
let b = 1
for (let i = 2; i <= n; i++) {
const next = a + b
a = b
b = next
steps++
}
console.log("fib(25) =", b)
console.log("pași de buclă:", steps)