De ce măsurăm algoritmii
Același program rulează repede pe un calculator nou și încet pe unul vechi. Așadar secundele sunt un mod slab de a compara doi algoritmi — numărul depinde de mașină, nu doar de cod.
În schimb numărăm pași: câte operații simple face algoritmul. Un pas este o acțiune mică, precum citirea unei valori, compararea a două numere sau adunarea lor.
Notația Big O descrie cum crește numărul de pași atunci când crește intrarea. Nu spune „asta durează 3 secunde”. Spune „dacă intrarea se dublează, munca se dublează” — adică O(n) — sau „dacă intrarea se dublează, munca rămâne aceeași” — adică O(1).
Big O se uită la cazul cel mai defavorabil: cei mai mulți pași de care algoritmul poate avea nevoie pentru o intrare de dimensiune n.
Numărarea pașilor
O buclă care trece prin fiecare element al unui tablou face o parcurgere pe element. Pentru 5 elemente sunt 5 pași, pentru 10 elemente 10 pași. Numărul de pași este același cu count($nums).
Nu ne interesează numărul exact. Ne interesează forma creșterii: intrare dublă, pași dubli. Această formă se numește liniară și se scrie O(n).
Numără pașii unei bucle
Funcția adaugă un contor $steps++ în interiorul buclei. Un tablou de 5 elemente cere 5 pași, un tablou de 10 elemente cere 10 pași — numărul urmează dimensiunea intrării.
Ieșire: script PHP
<?php
function countSteps(array $nums): int {
$steps = 0;
$sum = 0;
foreach ($nums as $n) {
$sum += $n;
$steps++;
}
echo "suma: $sum\n";
return $steps;
}
$small = [2, 4, 6, 8, 10];
$big = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
printf("pași pentru 5 elemente: %d\n", countSteps($small));
printf("pași pentru 10 elemente: %d\n", countSteps($big));
Dublarea intrării dublează munca
Programul execută aceeași buclă de numărare pentru n = 100, 200 și 400. De fiecare dată când n se dublează, se dublează și numărul de pași. Aceasta este amprenta lui O(n).
Ieșire: script PHP
<?php
foreach ([100, 200, 400] as $n) {
$steps = 0;
for ($i = 0; $i < $n; $i++) {
$steps++;
}
printf("n = %3d -> %3d pași\n", $n, $steps);
}
Clasele de creștere
Majoritatea algoritmilor se încadrează în câteva clase de creștere obișnuite, de la cea mai rapidă la cea mai lentă:
O(1) constantă — munca nu crește niciodată.O(log n) logaritmică — dublarea intrării adaugă un singur pas.O(n) liniară — munca crește odată cu intrarea.O(n log n) — un algoritm bun de sortare.O(n²) pătratică — o buclă în interiorul unei bucle.O(2ⁿ) exponențială — munca se dublează cu fiecare element în plus.
Pentru intrări mici diferența este minusculă. Pentru intrări mari ea decide dacă programul răspunde imediat sau nu se termină niciodată.
Compară clasele de creștere
Tabelul arată numărul de pași pentru valori tot mai mari ale lui n. La n = 16, log n este doar 4, în timp ce 2ⁿ este deja 65536. Cu cât n devine mai mare, cu atât clasele se depărtează una de alta.
Ieșire: script PHP
<?php
printf("%5s %7s %5s %9s %6s %8s\n", "n", "log n", "n", "n log n", "n^2", "2^n");
foreach ([1, 2, 4, 8, 16] as $n) {
$logn = log($n, 2);
printf("%5d %7.0f %5d %9.0f %6d %8d\n", $n, $logn, $n, $n * $logn, $n * $n, 2 ** $n);
}
Ce ignoră Big O
Big O păstrează doar forma creșterii și aruncă detaliile. O(2n), O(n + 5) și O(n) sunt toate aceeași clasă: liniară.
De ce? Pentru că la intrări mari factorul constant încetează să conteze. Un algoritm care face 2 parcurgeri peste un milion de elemente este totuși într-o cu totul altă lume decât unul care compară fiecare element cu fiecare alt element.
Regulile exacte de simplificare — renunță la constante, renunță la termenii mai mici — au propria lor pagină mai târziu în acest grup.
Două bucle sunt tot O(n)
Programul face două parcurgeri separate ale tabloului: una pentru sumă, una pentru cea mai mare valoare. Aceasta înseamnă 2n pași — 16 pentru 8 elemente. Big O renunță la constanta 2, deci aceasta este tot O(n).
Ieșire: script PHP
<?php
$nums = [3, 1, 4, 1, 5, 9, 2, 6];
$steps = 0;
$sum = 0;
foreach ($nums as $n) {
$sum += $n;
$steps++;
}
$max = $nums[0];
foreach ($nums as $n) {
if ($n > $max) {
$max = $n;
}
$steps++;
}
echo "suma: $sum\n";
echo "maximul: $max\n";
echo "elemente: ", count($nums), "\n";
echo "pași: $steps\n";