De ce contează?
Înainte de un meci, o echipă se antrenează săptămâni întregi — efort mare, o singură dată — ca în timpul jocului reacțiile să fie instantanee. Precalcularea funcționează la fel: investești o muncă mare la început, ca fiecare răspuns de mai târziu să vină pe loc.
Tiparul: muncă o dată, răspunsuri de multe ori
Precalcularea nu e un algoritm anume, ci o strategie: când o problemă cere același tip de răspuns de multe ori pe aceleași date, calculezi rezultatele o singură dată și le stochezi, ca apoi fiecare interogare să fie o citire rapidă.
Ai văzut-o deja la:
- ciurul lui Eratostene — toate primele până la
n, dintr-o trecere; - numărul de divizori — completat pentru toate numerele printr-un ciur;
- sumele parțiale (din alt capitol) — suma oricărui interval în
O(1)după o pregătireO(n).
Semnalul din enunț: cuvintele „q interogări", „pentru fiecare întrebare", „se dau t cazuri de test" pe același domeniu de valori. Acolo precalcularea transformă O(q · cost_mare) în O(pregătire + q).
Compromisul memorie–timp
Precalcularea cumpără timp cu memorie. Vectorul precalculat ocupă spațiu, dar fiecare interogare devine O(1) în loc de un calcul costisitor. De obicei e un schimb excelent — dar nu gratuit.
Pune-ți două întrebări înainte:
- Câte interogări sunt? Puține → poate nu merită; multe → aproape sigur merită.
- Încape vectorul în memorie? Un domeniu de
10⁸int-uri (~400 MB) depășește limita uzuală.
Când NU precalculezi
- Pentru o singură întrebare: un calcul direct e adesea mai rapid decât pregătirea întregului tabel.
- Când domeniul e prea mare ca să încapă în memorie (precalculezi pe tot intervalul degeaba).
- Când fiecare interogare e pe date diferite — precalcularea presupune un domeniu fix, reutilizat.
Greșeala 1 — precalculezi pentru o singură interogare: plătești pregătirea O(n log n) ca să răspunzi o dată. Pentru o întrebare unică, calculul direct O(√n) e mai bun.
Greșeala 2 — ignori memoria: alegi N uriaș „ca să fie sigur" și vectorul nu încape. Verifică întâi câtă memorie cere.
Greșeala 3 — recalculezi în buclă fără să-ți dai seama: ai precalculat, dar tot apelezi funcția costisitoare la fiecare interogare. Folosește vectorul gata calculat.
Greșeala 4 — precalculezi ce nu se reutilizează: dacă fiecare test are alt domeniu, tabelul precalculat nu se mai poate refolosi — câștigul dispare.
Recapitulare
- Precalcularea e o strategie: faci munca grea o dată, apoi răspunzi la fiecare interogare în O(1).
- Semnalul e „multe interogări pe același domeniu"; transformi
O(q · cost)înO(pregătire + q). - E un compromis memorie contra timp — nu o aplica pentru o singură întrebare sau când vectorul nu încape în memorie.