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 î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 din 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 generează î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 global numără fiecare apel. Calcularea lui fib(10) = 55 cere 177 de apeluri — pentru un singur număr mic. Arborele de apeluri se dublează la fiecare nivel.
Ieșire: program Go și rezultatul capturat
package main
import "fmt"
var calls = 0
func fib(n int) int {
calls++
if n < 2 {
return n
}
return fib(n-1) + fib(n-2)
}
func main() {
fmt.Println("fib(10) =", fib(10))
fmt.Println("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, 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ă 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 Go și rezultatul capturat
package main
import "fmt"
var calls = 0
func fib(n int) int {
calls++
if n < 2 {
return n
}
return fib(n-1) + fib(n-2)
}
func main() {
for _, n := range []int{5, 10, 15, 20, 25} {
calls = 0
fib(n)
fmt.Printf("fib(%2d) -> %7d apeluri\n", n, calls)
}
}
Soluția: o buclă
Problema nu este Fibonacci — problema este că aceleași valori sunt calculate iar și iar. O buclă care urcă 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 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ă prin ș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: program Go și rezultatul capturat
package main
import "fmt"
func main() {
n := 25
steps := 0
a, b := 0, 1
for i := 2; i <= n; i++ {
a, b = b, a+b
steps++
}
fmt.Println("fib(25) =", b)
fmt.Println("pași de buclă:", steps)
}