Când munca se dublează
O(2ⁿ) înseamnă timp exponențial: un singur element de intrare în plus dublează munca. Aceasta este clasa de creștere în care algoritmii încetează să fie utilizabili — nu pentru intrări uriașe, ci deja pentru unele medii.
Munca exponențială vine de obicei din recursivitate care se ramifică: o funcție care se apelează pe sine 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 Fibonacci începe cu 0, 1, iar fiecare număr următor este suma celor două de 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 încă două, iar aceleași valori sunt calculate iar și iar. Numai fib(2) este recalculat de mii de ori într-un apel mai mare.
Fibonacci cu recursivitate
Un contor transmis prin referință numără fiecare apel. Calculul fib(10) = 55 cere 177 de apeluri — pentru un singur număr mic. Arborele de apeluri se dublează la fiecare nivel.
Ieșire: script PHP
<?php
function fib(int $n, int &$calls): int {
$calls++;
if ($n < 2) {
return $n;
}
return fib($n - 1, $calls) + fib($n - 2, $calls);
}
$calls = 0;
echo "fib(10) = ", fib(10, $calls), "\n";
echo "apeluri de funcție: ", $calls, "\n";
De ce explodează
Urmărește numărul de apeluri în timp ce n crește în pași de 5. Nu crește în 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 inofensiv, iar testele mici se termină instantaneu.
Numărăm apelurile în timp 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: script PHP
<?php
function fib(int $n, int &$calls): int {
$calls++;
if ($n < 2) {
return $n;
}
return fib($n - 1, $calls) + fib($n - 2, $calls);
}
foreach ([5, 10, 15, 20, 25] as $n) {
$calls = 0;
fib($n, $calls);
printf("fib(%2d) -> %7d apeluri\n", $n, $calls);
}
Soluția: o buclă
Problema nu este Fibonacci — este calcularea acelorași valori de nenumărate ori. O buclă care urcă de la 0 și 1, păstrând doar ultimele două valori, calculează fiecare număr exact o dată.
Asta 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 pentru asta există 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ă a avut nevoie de 242.785 de apeluri pentru același răspuns.
Ieșire: script PHP
<?php
$n = 25;
$steps = 0;
$a = 0;
$b = 1;
for ($i = 2; $i <= $n; $i++) {
[$a, $b] = [$b, $a + $b];
$steps++;
}
echo "fib(25) = ", $b, "\n";
echo "pași de buclă: ", $steps, "\n";