Patru reguli simple
Ca să transformi „câți pași face acest cod” într-o clasă Big O ai nevoie de patru reguli:
1. Păstrează cazul cel mai rău — numără cei mai mulți pași pe care codul îi poate cere vreodată.
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 câte 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 devreme. Cazul cel mai rău este promisiunea pe care algoritmul o poate respecta întotdeauna.
Cazul cel mai bun și cazul 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ă cifra 5: căutarea liniară este O(n).
Ieșire: program TypeScript și rezultatul capturat
function search(words: string[], target: string): number {
let steps = 0
for (const word of words) {
steps++
if (word === target) {
break
}
}
return steps
}
const words = ["one", "two", "three", "four", "five"]
console.log('cazul cel mai bun ("one"):', search(words, "one"), "pas")
console.log('cazul cel mai rău ("six"):', search(words, "six"), "pași")
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 rămâne aceeași: dublezi intrarea, se dublează pașii.
Big O păstrează doar forma, așa că O(n/2), O(n) și O(2n) sunt toate aceeași clasă: liniară.
Jumătate din pași înseamnă tot O(n)
Bucla sare câte 2 și vizitează 4 dintre cele 8 elemente. Dacă tabloul se dublează, se dublează și pașii — deci n/2 pași înseamnă tot creștere liniară, O(n).
Ieșire: program TypeScript și rezultatul capturat
const nums = [3, 1, 4, 1, 5, 9, 2, 6]
const visited: number[] = []
let steps = 0
// Vizităm fiecare al doilea element: n/2 pași.
for (let i = 0; i < nums.length; i += 2) {
visited.push(nums[i])
steps++
}
console.log(visited.join(" "))
console.log("elemente:", nums.length, "pași:", steps)
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².
Pe măsură ce n crește, partea n² înghite restul — la n = 1000 sunt un milion de pași față de o mie. Big O păstrează doar termenul care crește cel mai repede: O(n + n²) devine O(n²).
n + n² pași
Pentru 6 elemente bucla simplă adaugă 6 pași, iar buclele imbricate adaugă 36 — în total 42. Termenul la pătrat domină deja, iar avansul lui crește odată cu n.
Ieșire: program TypeScript și rezultatul capturat
const nums = [1, 2, 3, 4, 5, 6]
const n = nums.length
let steps = 0
// O buclă simplă: n pași.
for (let i = 0; i < n; i++) {
steps++
}
// O buclă în interiorul altei bucle: n * n pași.
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
steps++
}
}
console.log("n =", n)
console.log("n + n*n =", steps)
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. Să numim 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 înseamnă 6 pași. Complexitatea este O(a · b) — dacă tabloul de animale crește, iar cel de culori nu, contează doar b.
Ieșire: program TypeScript și rezultatul capturat
const colors = ["roșu", "verde", "albastru"]
const animals = ["pisică", "câine"]
let steps = 0
for (let i = 0; i < colors.length; i++) {
for (let j = 0; j < animals.length; j++) {
steps++
}
}
console.log("culori:", colors.length, "animale:", animals.length)
console.log("pași:", steps)
Limitele lui Big O
Big O este un instrument aproximativ în mod intenționat ș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 „mai lent” O(n²) cu pași mărunți poate învinge unul „mai rapid” O(n) cu pași grei.
Folosește Big O ca să compari cum scalează algoritmii. Pentru viteză reală pe date reale, măsoară.