Notația Big O în Python

Același program rulează repede pe un calculator nou și încet pe unul vechi. De aceea secundele sunt un mod prost de a compara doi algoritmi — numărul depinde de mașină, nu doar de cod.

În schimb, numărăm pașii: câte operații simple face algoritmul. Un pas este o acțiune mică, cum ar fi 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 cresc datele de intrare. Ea nu spune „asta durează 3 secunde”. Ea spune „dacă datele de intrare se dublează, munca se dublează” — aceasta este O(n) — sau „dacă datele de intrare se dublează, munca rămâne aceeași” — aceasta este O(1).

Big O se uită la cazul cel mai defavorabil: cel mai mare număr de pași de care algoritmul poate avea vreodată nevoie pentru date de intrare de mărime n.

O buclă care vizitează fiecare element al unei liste face câte o trecere pentru fiecare element. Pentru 5 elemente sunt 5 pași, pentru 10 elemente — 10 pași. Numărul de pași este egal cu len(nums).

Nu ne interesează numărul exact. Ne interesează forma creșterii: date de intrare de două ori mai mari, de două ori mai mulți pași. Această formă se numește liniară și se scrie O(n).

Funcția mărește un contor steps în interiorul buclei. O listă de 5 elemente are nevoie de 5 pași, o listă de 10 elemente are nevoie de 10 pași — numărul urmează mărimea datelor de intrare.

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).

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 datelor de intrare adaugă doar un pas.
O(n) liniar — munca crește odată cu datele de intrare.
O(n log n) — un algoritm de sortare bun.
O(n²) pătratic — o buclă în interiorul altei bucle.
O(2ⁿ) exponențial — munca se dublează cu fiecare element în plus.

Pentru date de intrare mici diferența este neînsemnată. Pentru date de intrare mari ea decide dacă programul răspunde imediat sau nu termină niciodată.

Tabelul arată numărul de pași pentru n tot mai mare. 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 depărtează mai mult una de alta.

Big O păstrează doar forma creșterii și aruncă detaliile. O(2n), O(n + 5) și O(n) sunt toate aceeași clasă: liniară.

De ce? Pentru că, la date de intrare mari, factorul constant nu mai contează. Un algoritm care face 2 treceri peste un milion de elemente este totuși într-o cu totul altă lume decât unul care compară fiecare element cu fiecare alt element.

Regulile exacte de simplificare — eliminarea constantelor, eliminarea termenilor mai mici — au propria lor pagină, mai târziu în acest grup.

Programul face două treceri separate peste listă: una pentru sumă, una pentru cea mai mare valoare. Asta înseamnă 2n pași — 16 pentru 8 elemente. Big O elimină constanta 2, deci acesta este tot O(n).