Algoritmi care se termină la timp: o verificare rapidă a complexității

Scrii o funcție, o rulezi pe datele de test și funcționează bine. Apoi ajunge în producție — 500.000 de rânduri în loc de 500 — și cererea expiră. Asta se întâmplă constant, și este aproape întotdeauna o problemă de complexitate ascunsă în spatele codului care arăta rezonabil la scară mică.

De ce laptop-ul tău te-a minținit

Un algoritm O(n²) care rulează pe 100 de elemente face 10.000 de operații. Asta e instantaneu pe orice mașină. Rulează același algoritm pe 100.000 de elemente și ajungi la 10 miliarde de operații — minute sau ore în loc de milisecunde. Saltul de la n la n² nu pare periculos până când n devine mare, ceea ce este exact de ce trece prin code review și testarea locală.

Un exemplu clasic: verificarea pentru duplicate-uri cu o buclă imbricată.

def has_duplicates(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

Aceasta este O(n²). Înlocuiește-o cu un set:

def has_duplicates(items):
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False

Acum este O(n). Căutările în set sunt în medie O(1), deci întreaga funcție se scalează liniar în loc de pătratic. Pe 10.000 de elemente asta e diferența între aproximativ 100 de milioane de comparații și 10.000.

Măsoară înainte să optimizezi

Nu ghici. Folosește timeit pentru microbenchmarkuri:

import timeit
timeit.timeit(lambda: has_duplicates(list(range(5000))), number=10)

Pentru funcții mai mari, profilează cu cProfile:

python -m cProfile -s cumulative myscript.py

Privește coloana cumtime. Dacă o funcție consumă 90% din runtime, asta e ținta ta. Optimizarea codului care nu este gâtul de sticlă îți risipește timpul și adaugă complexitate fără nici un câștig.

Modele comune care tăcut devin lente

Verificări repetate de apartenență la listă. if x in my_list este O(n) pentru o listă dar O(1) în medie pentru un set sau dict. Dacă verifici apartenența într-o buclă, acea verificare O(n) într-o buclă O(n) îți dă O(n²) în total. Înlocuiește lista cu un set și ești înapoi la O(n).

Concatenarea șirurilor de caractere într-o buclă. În Python, result += chunk într-o buclă asupra șirurilor este O(n²) în cel mai rău caz deoarece șirurile sunt imuabile și fiecare concatenare copiază tot lucrul. Folosește ''.join(chunks) în schimb — construiește șirul o dată.

Sortarea când nu ai nevoie de ea. sorted() este O(n log n). Dacă o apelezi într-o buclă doar ca să găsești max sau min în fiecare iterație, folosește max()/min() (O(n)) sau mai bine, un heap (heapq) dacă ai nevoie de extrema în curs de execuție în mod repetat. heapq.nlargest(k, data) este O(n log k), mult mai ieftin decât sortarea listei întregi când k este mic.

Funcții recursive fără memoizare. Fibonacci recursiv naiv este O(2ⁿ) pentru că recomputează aceleași subprobleme din nou și din nou. Adaugă functools.lru_cache și scade la O(n):

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Citirea Big O dintr-un cod real, rapid

Numără buclele imbricante peste aceeași intrare — asta e de obicei exponenul tău. O buclă simplă este O(n). O buclă într-o buclă este O(n²) decât dacă intervalul buclei interioare se micșorează (ca în forma optimizată a bubble sort, încă O(n²) în cel mai rău caz dar mai puține comparații). Apelurile recursive care împart problema în două, cum ar fi căutarea binară sau merge sort, indică O(log n) sau O(n log n). Apelurile recursive care se ramifică în apeluri multiple pe nivel, cum ar fi Fibonacci naiv, indică timp exponențial — un semnal puternic că ai nevoie de memoizare sau o rescriire iterativă.

O obicei bun: înainte să scrii buclele imbricante sau recursivitate peste date cu vizibilitate utilizator, întreabă-te ce ar putea fi n în mod realist în producție, nu în fișierul tău de test. Dacă n ar putea ajunge la sase cifre, o soluție O(n²) are nevoie de o a doua privire înainte să se lanseze.

Pentru mai multe pe tema analizei complexității, algoritmi de sortare și instrumente de profilare, verifică segmentele Python și Computer Science pe Korra Studio.