Patru reguli simple
Transformarea întrebării „câți pași face acest cod” într-o clasă Big O cere patru reguli:
1. Păstrează cazul cel mai rău — numără cei mai mulți pași de care poate avea nevoie codul.
2. Renunță la constante — O(2n) și O(n/2) sunt amândouă O(n).
3. Renunță la termenii mai mici — O(n + n²) este O(n²).
4. Intrări diferite primesc litere diferite — două tablouri diferite dau O(a · b), nu O(n²).
Fiecare regulă are mai jos un exemplu.
Regula 1: păstrează cazul cel mai rău
O căutare liniară poate avea noroc: dacă valoarea se află la început, un singur pas este de ajuns. Big O ignoră norocul și descrie cazul cel mai rău al tabloului — valoarea este ultima sau lipsește, iar toate cele n elemente sunt verificate.
Așadar o căutare liniară este O(n), chiar dacă deseori se termină mai repede. Cazul cel mai rău este promisiunea pe care algoritmul o poate respecta întotdeauna.
Cazul cel mai bun și cel mai rău al unei căutări
Căutarea primului cuvânt ia 1 pas. Căutarea unui cuvânt lipsă ia toți cei 5. Big O păstrează cei 5: căutarea liniară este O(n).
Ieșire: script PHP
<?php
function search(array $words, string $target): int {
$steps = 0;
foreach ($words as $w) {
$steps++;
if ($w === $target) {
break;
}
}
return $steps;
}
$words = ["one", "two", "three", "four", "five"];
echo 'cazul cel mai bun ("one"): ', search($words, "one"), " pas\n";
echo 'cazul cel mai rău ("six"): ', search($words, "six"), " pași\n";
Regula 2: renunță la constante
O buclă care vizitează fiecare al doilea element face n/2 pași. Jumătate din muncă — dar forma creșterii este neschimbată: dublezi intrarea, se dublează pașii.
Big O păstrează doar forma, deci O(n/2), O(n) și O(2n) sunt toate aceeași clasă: liniară.
Jumătate din pași este tot O(n)
Bucla sare cu 2 și vizitează 4 din cele 8 elemente. Dacă tabloul se dublează, se dublează și pașii — așadar n/2 pași este tot creștere liniară, O(n).
Ieșire: script PHP
<?php
$nums = [3, 1, 4, 1, 5, 9, 2, 6];
$steps = 0;
// Vizităm fiecare al doilea element: n/2 pași.
for ($i = 0; $i < count($nums); $i += 2) {
echo $nums[$i], " ";
$steps++;
}
echo "\n";
echo "elemente: ", count($nums), " pași: ", $steps, "\n";
Regula 3: renunță la termenii mai mici
Codul amestecă deseori părți cu costuri diferite: o buclă simplă (n pași) urmată de bucle imbricate (n² pași). Totalul este n + n².
Când n crește, partea n² înghite restul — la n = 1000 este un milion de pași față de o mie. Big O păstrează doar termenul cu cea mai rapidă creștere: O(n + n²) devine O(n²).
n + n² pași
Pentru 6 elemente bucla simplă adaugă 6 pași, iar buclele imbricate adaugă 36 — 42 în total. Termenul pătratic domină deja, iar avansul lui crește odată cu n.
Ieșire: script PHP
<?php
$nums = [1, 2, 3, 4, 5, 6];
$steps = 0;
// O buclă simplă: n pași.
foreach ($nums as $x) {
$steps++;
}
// O buclă în interiorul unei bucle: n * n pași.
foreach ($nums as $x) {
foreach ($nums as $y) {
$steps++;
}
}
echo "n = ", count($nums), "\n";
echo "n + n*n = ", $steps, "\n";
Regula 4: intrări diferite, litere diferite
Când buclele imbricate parcurg două intrări diferite, numărul de pași este a · b — cele două lungimi înmulțite. A numi asta O(n²) ar fi greșit: intrările pot avea dimensiuni foarte diferite.
Clasa corectă este O(a · b). Devine O(n²) doar în cazul special în care ambele intrări sunt una și aceeași.
Două tablouri diferite
3 culori ori 2 animale fac 6 pași. Complexitatea este O(a · b) — dacă tabloul de animale crește, iar cel de culori nu, contează doar b.
Ieșire: script PHP
<?php
$colors = ["red", "green", "blue"];
$animals = ["cat", "dog"];
$steps = 0;
foreach ($colors as $c) {
foreach ($animals as $a) {
$steps++;
}
}
echo "culori: ", count($colors), " animale: ", count($animals), "\n";
echo "pași: ", $steps, "\n";
Limitele lui Big O
Big O este intenționat un instrument aproximativ și merită să știi ce ascunde.
Vede doar cazul cel mai rău. Un algoritm cu un caz cel mai rău înspăimântător poate fi excelent în practică, dacă acel caz este rar. Uneori cazul mediu este numărul care contează.
Ignoră constantele. Pe hârtie, 1000 · n și n sunt aceeași clasă. Pentru intrări mici, un algoritm O(n²) „mai lent”, dar cu pași minusculi, poate învinge unul O(n) „mai rapid”, cu pași grei.
Folosește Big O pentru a compara cum scalează algoritmii. Pentru viteza reală pe date reale, măsoară.