Patru reguli simple
Transformarea întrebării „câți pași face acest cod” într-o clasă Big O se face cu 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ă slice-uri diferite dau O(a · b), nu O(n²).
Fiecare regulă are câte un exemplu mai jos.
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 slice-ului — valoarea este ultima sau lipsește, iar toate cele n elemente sunt verificate.
Așadar, o căutare liniară este O(n), chiar dacă de multe ori 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 ale unei căutări
Căutarea primului cuvânt ia 1 pas. Căutarea unui cuvânt care lipsește ia toți cei 5 pași. Big O păstrează cifra 5: căutarea liniară este O(n).
Ieșire: program Go și rezultatul capturat
package main
import "fmt"
func search(words []string, target string) int {
steps := 0
for _, w := range words {
steps++
if w == target {
break
}
}
return steps
}
func main() {
words := []string{"one", "two", "three", "four", "five"}
fmt.Println("cazul cel mai bun („one”):", search(words, "one"), "pas")
fmt.Println("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ă și pașii.
Big O păstrează doar forma, așa că O(n/2), O(n) și O(2n) sunt toate din aceeași clasă: liniară.
Jumătate din pași înseamnă tot O(n)
Bucla sare din 2 în 2 și vizitează 4 din cele 8 elemente. Dacă slice-ul se dublează, se dublează și pașii — deci n/2 pași înseamnă tot creștere liniară, O(n).
Ieșire: program Go și rezultatul capturat
package main
import "fmt"
func main() {
nums := []int{3, 1, 4, 1, 5, 9, 2, 6}
steps := 0
// Vizitează fiecare al doilea element: n/2 pași.
for i := 0; i < len(nums); i += 2 {
fmt.Print(nums[i], " ")
steps++
}
fmt.Println()
fmt.Println("elemente:", len(nums), "pași:", steps)
}
Regula 3: renunță la termenii mai mici
Codul combină adesea 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 înseamnă 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 — 42 în total. Termenul la pătrat domină deja, iar avansul lui crește odată cu n.
Ieșire: program Go și rezultatul capturat
package main
import "fmt"
func main() {
nums := []int{1, 2, 3, 4, 5, 6}
steps := 0
// O buclă simplă: n pași.
for range nums {
steps++
}
// O buclă în interiorul altei bucle: n * n pași.
for range nums {
for range nums {
steps++
}
}
fmt.Println("n =", len(nums))
fmt.Println("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. Dacă am 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ă slice-uri diferite
3 culori ori 2 animale înseamnă 6 pași. Complexitatea este O(a · b) — dacă slice-ul de animale crește, iar cel de culori nu, contează doar b.
Ieșire: program Go și rezultatul capturat
package main
import "fmt"
func main() {
colors := []string{"roșu", "verde", "albastru"}
animals := []string{"pisică", "câine"}
steps := 0
for range colors {
for range animals {
steps++
}
}
fmt.Println("culori:", len(colors), "animale:", len(animals))
fmt.Println("pași:", steps)
}
Limitele notației Big O
Big O este, în mod intenționat, un instrument aproximativ și merită să știi ce ascunde.
Vede doar cazul cel mai rău. Un algoritm cu un caz nefavorabil înspăimântător poate fi excelent în practică, dacă acel caz este rar. Uneori, cazul mediu este cifra care contează.
Ignoră constantele. Pe hârtie, 1000 · n și n sunt din aceeași clasă. Pentru intrări mici, un algoritm „mai lent”, O(n²), cu pași mărunți, poate să învingă 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ă.