Algoritmi eficienți la Subiectul III: cum iei punctajul pe eficiență

Ultimul item de la BAC informatică (Subiectul III, itemul 3) are o particularitate: nu e suficient ca programul să dea rezultatul corect. Enunțul cere „un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate”, iar în modelul actual itemul are două părți: a) descrierea în limbaj natural a algoritmului și justificarea eficienței (2 puncte) și b) programul C++ (8 puncte). Verifică întotdeauna ultimul model oficial pe subiecte.edu.ro, dar ideea de fond rămâne aceeași: o soluție corectă care nu e eficientă primește, în general, doar o parte din punctaj.

Ce înseamnă concret „eficient”

Datele de la acest item sunt de obicei mari: până la un milion de numere într-un fișier, cu valori de până la un miliard. Asta îți dă două semnale:

• Timp: un algoritm care compară fiecare număr cu fiecare alt număr face aproximativ n² operații. Pentru n = 1 000 000, asta înseamnă 10¹² pași — mult prea mult. Ținta este o singură parcurgere a datelor (complexitate O(n)) sau, când e cazul, o parcurgere a datelor plus o parcurgere a unui interval mic de valori.
• Memorie: dacă rezultatul se poate calcula pe măsură ce citești, nu memorezi șirul într-un vector. Folosești doar câteva variabile simple sau un vector a cărui dimensiune depinde de intervalul valorilor, nu de numărul lor.

Practic, întrebarea pe care ți-o pui la fiecare problemă este: „Pot afla răspunsul citind numerele o singură dată, de la stânga la dreapta, și păstrând doar ce e strict necesar?” De cele mai multe ori, răspunsul e da.

Cele trei tehnici care rezolvă majoritatea problemelor

Restricțiile din enunț („numere naturale din intervalul [1, 1000]”, „șirul este ordonat crescător”) nu sunt decor: sunt indiciul pentru tehnica pe care trebuie să o folosești. Dacă vezi un interval mic, aproape sigur e un vector de frecvență.

Exemplul 1: valoarea care apare cel mai des

Fișierul bac.txt conține un șir de cel mult 10⁶ numere naturale din intervalul [1, 1000]. Se cere să se afișeze pe ecran valoarea care apare de cele mai multe ori în șir; dacă sunt mai multe astfel de valori, se afișează cea mai mică.

Soluția neeficientă ar memora toate numerele și, pentru fiecare, ar număra de câte ori mai apare — n² comparații. Soluția eficientă folosește faptul că valorile sunt cel mult 1000:

#include <iostream>
#include <fstream>
using namespace std;

int fr[1001];

int main()
{
    ifstream f("bac.txt");
    int x, v, vmax = 0;
    while (f >> x)
        fr[x]++;
    for (v = 1; v <= 1000; v++)
        if (fr[v] > fr[vmax])
            vmax = v;
    cout << vmax;
    return 0;
}

Pentru fișierul 5 3 5 7 3 5 se obțin fr[3] = 2, fr[5] = 3, fr[7] = 1 și se afișează 5. Pentru 4 2 4 2, fr[2] = fr[4] = 2; parcurgerea crescătoare cu comparația strictă > păstrează primul maxim găsit, deci se afișează 2, exact cum cere enunțul. Variabila vmax pornește de la 0, iar fr[0] rămâne 0 pentru că valorile sunt cel puțin 1.

Descrierea algoritmului (cum ai scrie-o la punctul a):

„Se citesc pe rând numerele din fișier și, pentru fiecare număr x, se incrementează fr[x], unde fr este un vector de frecvență cu 1001 elemente. Apoi se parcurge vectorul crescător și se reține prima valoare cu frecvența maximă. Algoritmul este eficient ca timp, deoarece fișierul este parcurs o singură dată, iar vectorul de frecvență are dimensiune constantă (1000), deci complexitatea este O(n). Este eficient ca memorie, deoarece nu se memorează șirul, ci doar frecvențele celor 1000 de valori posibile.”

Exemplul 2: șir ordonat — valori distincte

Fișierul bac.txt conține un șir de cel mult 10⁶ numere naturale din intervalul [0, 10⁹], ordonat crescător. Se cere numărul de valori distincte din șir.

Aici intervalul e uriaș, deci un vector de frecvență nu are sens. Dar șirul e ordonat: valorile egale stau una lângă alta. O valoare e „nouă” exact atunci când diferă de cea dinaintea ei.

#include <iostream>
#include <fstream>
using namespace std;

int main()
{
    ifstream f("bac.txt");
    int x, ant, nr = 0;
    if (f >> ant)
    {
        nr = 1;
        while (f >> x)
        {
            if (x != ant) nr++;
            ant = x;
        }
    }
    cout << nr;
    return 0;
}

Pentru 1 1 3 5 5 5 9 se afișează 4 (valorile 1, 3, 5, 9). Memoria folosită: trei variabile întregi, oricât de mare ar fi fișierul.

Descriere: „Se citește primul număr, apoi, pe rând, celelalte; deoarece șirul este ordonat crescător, o valoare apare pentru prima dată atunci când diferă de valoarea citită anterior, caz în care se incrementează contorul. Algoritmul parcurge fișierul o singură dată (timp liniar) și folosește un număr constant de variabile, fără a memora șirul.”

Cum scrii descrierea ca să iei cele 2 puncte

Nu e nevoie de un eseu. Trei sau patru propoziții care conțin:

1. ideea — ce faci cu fiecare număr citit (îl numeri, îl compari cu anteriorul, îl adaugi la o sumă);
2. structurile folosite — un vector de frecvență și dimensiunea lui, sau doar variabile simple;
3. justificarea timpului — o singură parcurgere a fișierului, complexitate liniară;
4. justificarea memoriei — șirul nu e memorat; memoria nu depinde de numărul de valori citite.

Descrierea trebuie să corespundă programului tău. O descriere a unui algoritm liniar, însoțită de un program cu două bucle imbricate peste toate valorile, nu convinge pe nimeni.

Capcane frecvente

• Vectori uriași „ca să fie”: un vector de 10⁹ elemente nu încape în memorie. Vectorul de frecvență merge doar când intervalul valorilor e mic.
• Sortarea datelor cu metoda bulelor sau prin selecție: e O(n²), deci tocmai ce trebuia evitat. Dacă ai nevoie de ordine și valorile sunt mici, frecvențele îți dau ordinea gratuit.
• Depășiri: sumele sau produsele unor numere mari se țin în long long.
• Vector de frecvență local: declarat în main, nu e inițializat cu 0. Declară-l global, cum am făcut mai sus.