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. Ea nu spune „asta durează 3 secunde”. Ea 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 poate avea nevoie vreodată algoritmul pentru o intrare de dimensiune n.
Numărarea pașilor
O buclă care vizitează fiecare element al unui tablou face o trecere pentru fiecare element. Pentru 5 elemente înseamnă 5 pași, pentru 10 elemente 10 pași. Numărul de pași este același cu nums.length.
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: program TypeScript și rezultatul capturat
function countSteps(nums: number[]): number {
let steps = 0
let sum = 0
for (const n of nums) {
sum += n
steps++
}
console.log("suma:", sum)
return steps
}
const small = [2, 4, 6, 8, 10]
const big = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
console.log("pași pentru 5 elemente:", countSteps(small))
console.log("pași pentru 10 elemente:", countSteps(big))
Dublarea intrării dublează munca
Programul rulează 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: program TypeScript și rezultatul capturat
const pad = (value: number, width: number): string => String(value).padStart(width)
for (const n of [100, 200, 400]) {
let steps = 0
for (let i = 0; i < n; i++) {
steps++
}
console.log(`n = ${pad(n, 3)} -> ${pad(steps, 3)} pași`)
}
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 altei 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 un n care crește. 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 îndepărtează mai mult una de alta.
Ieșire: program TypeScript și rezultatul capturat
const pad = (value: string | number, width: number): string => String(value).padStart(width)
console.log(pad("n", 5), pad("log n", 7), pad("n", 5), pad("n log n", 9), pad("n^2", 6), pad("2^n", 8))
for (const n of [1, 2, 4, 8, 16]) {
const logn = Math.log2(n)
console.log(
pad(n, 5),
pad(logn.toFixed(0), 7),
pad(n, 5),
pad((n * logn).toFixed(0), 9),
pad(n * n, 6),
pad(2 ** n, 8),
)
}
Ce ignoră Big O
Big O păstrează doar forma creșterii și aruncă detaliile. O(2n), O(n + 5) și O(n) fac toate parte din aceeași clasă: liniară.
De ce? Pentru că la intrări mari factorul constant încetează să conteze. Un algoritm care face 2 treceri peste un milion de elemente este oricum î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 înseamnă tot O(n)
Programul face două parcurgeri separate ale tabloului: una pentru sumă, una pentru cea mai mare valoare. Asta înseamnă 2n pași — 16 pentru 8 elemente. Big O renunță la constanta 2, deci acest lucru înseamnă tot O(n).
Ieșire: program TypeScript și rezultatul capturat
const nums = [3, 1, 4, 1, 5, 9, 2, 6]
let steps = 0
// Parcurgerea 1: suma.
let sum = 0
for (const n of nums) {
sum += n
steps++
}
// Parcurgerea 2: cea mai mare valoare.
let biggest = nums[0]
for (const n of nums) {
if (n > biggest) {
biggest = n
}
steps++
}
console.log("suma:", sum)
console.log("maxim:", biggest)
console.log("elemente:", nums.length)
console.log("pași:", steps)