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 de care codul poate avea vreodată nevoie.
2. Elimină constantele — O(2n) și O(n/2) sunt ambele O(n).
3. Elimină termenii mai mici — O(n + n²) este O(n²).
4. Intrări diferite primesc litere diferite — două liste 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 suficient. Big O ignoră norocul și descrie cazul cel mai rău al listei — 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 durează 1 pas. Căutarea unui cuvânt care lipsește durează toți cei 5. Big O îi păstrează pe cei 5: căutarea liniară este O(n).
Ieșire: program Python complet
def search(words, target):
steps = 0
for w in words:
steps += 1
if w == target:
break
return steps
words = ["one", "two", "three", "four", "five"]
print('cazul cel mai bun ("one"):', search(words, "one"), "pas")
print('cazul cel mai rău ("six"):', search(words, "six"), "pași")
Regula 2: Elimină constantele
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, deci O(n/2), O(n) și O(2n) sunt toate aceeași clasă: timp liniar.
Jumătate din pași este tot O(n)
Bucla sare cu 2 și vizitează 4 din cele 8 elemente. Dacă lista se dublează, se dublează și pașii — deci n/2 pași înseamnă tot o creștere liniară, O(n).
Ieșire: program Python complet
nums = [3, 1, 4, 1, 5, 9, 2, 6]
steps = 0
# Vizităm fiecare al doilea element: n/2 pași.
for i in range(0, len(nums), 2):
print(nums[i], end=" ")
steps += 1
print()
print("elemente:", len(nums), "pași:", steps)
Regula 3: Elimină 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² o înghite pe 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 pătratic domină deja, iar avansul lui doar crește odată cu n.
Ieșire: program Python complet
nums = [1, 2, 3, 4, 5, 6]
steps = 0
# O buclă simplă: n pași.
for n in nums:
steps += 1
# O buclă în interiorul altei bucle: n * n pași.
for x in nums:
for y in nums:
steps += 1
print("n =", len(nums))
print("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. Ar fi greșit să-l numim O(n²): intrările pot avea dimensiuni foarte diferite.
Clasa corectă este O(a · b). Ea devine O(n²) doar în cazul special în care ambele intrări sunt una și aceeași.
Două liste diferite
3 culori ori 2 animale înseamnă 6 pași. Complexitatea este O(a · b) — dacă lista de animale crește, iar lista de culori nu, contează doar b.
Ieșire: program Python complet
colors = ["red", "green", "blue"]
animals = ["cat", "dog"]
steps = 0
for c in colors:
for a in animals:
steps += 1
print("culori:", len(colors), "animale:", len(animals))
print("pași:", steps)
Limitele 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 înfricoșă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 îl poate întrece pe unul „mai rapid” O(n) cu pași grei.
Folosește Big O ca să compari cum se scalează algoritmii. Pentru viteza reală pe date reale, măsoară.