Complexitatea la BAC: bucle, timp și memorie

Pentru a estima eficiența unui algoritm la BAC, identifici dimensiunea datelor și numeri de câte ori se execută operația repetată. Două bucle scrise una lângă alta își adună costurile; două bucle imbricate pot multiplica numărul de pași, dar trebuie citite limitele lor. Numărul liniilor de cod nu măsoară timpul de execuție.

Lecția folosește modele elementare de numărare a operațiilor, utile pentru justificarea eficienței unei soluții. Notația asimptotică este explicată prin exemple, fără a înlocui cerința concretă a subiectului. Verifică programa profilului și modul în care enunțul cere justificarea timpului și memoriei.

Care este dimensiunea datelor?

Dacă primești un șir cu n numere, n este de obicei dimensiunea relevantă. Dacă primești o matrice cu n linii și m coloane, ai două dimensiuni, iar parcurgerea tuturor elementelor cere n ori m vizite.

Pentru un singur număr natural, poți măsura mărimea prin valoarea lui sau prin numărul cifrelor. O buclă care elimină pe rând cifrele face un pas pentru fiecare cifră, nu un pas pentru fiecare unitate din valoarea numărului.

Precizează întotdeauna ce înseamnă variabila din estimare. Expresia „liniar” nu este completă dacă nu spui în raport cu ce mărime. Un algoritm liniar în numărul elementelor poate fi suficient, în timp ce unul liniar în valoarea unui prag foarte mare poate fi nepotrivit.

O buclă simplă: număr exact și ordin de creștere

Considerăm următoarea schemă, pentru n natural pozitiv. Operația urmărită este apelul abstract „prelucrează”, presupus cu un cost constant.

pentru i de la 1 la n
    prelucrează un element

Operația se execută exact de n ori. Dacă dublezi numărul elementelor, dublezi numărul acestor execuții. Spunem că numărul operațiilor crește liniar; o descriere precisă a ordinului este Θ(n).

Notația O(n) exprimă o limită superioară de ordin liniar și este folosită frecvent în explicații școlare. Când afirmăm aici că un cost este liniar sau pătratic, avem în vedere ordinul efectiv al numărului de operații descrise, nu numai o limită mai largă care ar fi și ea adevărată.

Două bucle succesive nu formează automat un pătrat

pentru i de la 1 la n
    operația A
pentru j de la 1 la n
    operația B

Avem n execuții ale primei operații și n ale celei de-a doua, deci două ori n în total. Costul rămâne liniar. Constanta doi influențează durata practică, dar nu schimbă felul în care numărul de operații crește odată cu n.

Dacă prima buclă merge până la n și a doua până la m, costul este proporțional cu n+m. Nu înlocui cele două dimensiuni cu una singură decât dacă enunțul stabilește o relație între ele.

Într-o justificare scrisă, spune ce face fiecare trecere: de exemplu, prima află minimul, iar a doua afișează pozițiile lui. Astfel arăți că parcurgi vectorul de două ori, nu că verifici toate perechile de poziții.

Bucle imbricate: citește limita interioară

pentru i de la 1 la n
    pentru j de la 1 la n
        prelucrează perechea (i,j)

Pentru fiecare dintre cele n valori ale lui i, bucla interioară execută n pași. Totalul este n². Dublarea lui n produce de patru ori mai multe perechi, ceea ce explică diferența față de două parcurgeri succesive.

Schimbăm acum limita interioară: j merge de la unu la i. Numărul de operații devine unu plus doi și așa mai departe până la n, adică n(n+1)/2. Ordinul rămâne pătratic, deși numărul exact este diferit.

n	Două bucle succesive	Două bucle complete imbricate	Buclă interioară până la i
4	8	16	10
8	16	64	36
10	20	100	55

Tabelul nu măsoară secunde. El numără operația aleasă în trei scheme diferite. Durata în secunde depinde și de implementare, hardware și costul efectiv al operației, deci nu promite un timp exact numai pe baza ordinului.

Împărțirea repetată schimbă scara

Pornim de la x=n, cu n pozitiv, și înlocuim repetat x cu partea întreagă a lui x/2 până când x devine zero. Pentru n=13, valorile pozitive prelucrate sunt treisprezece, șase, trei și unu: patru pași.

Pentru n=16, valorile sunt șaisprezece, opt, patru, doi și unu: cinci pași. Numărul de pași crește numai cu aproximativ unu când dublezi n. Costul este logaritmic în valoarea inițială a lui n.

Dacă împarți la zece, numărul pașilor pentru un număr pozitiv este numărul cifrelor zecimale. Cazul zero trebuie tratat conform buclei folosite: o buclă cu test inițial poate avea zero execuții, iar o variantă care procesează explicit cifra zero are o execuție.

O buclă interioară poate parcurge în total doar n elemente

Nu orice două bucle vizibile cer automat timp pătratic. Imaginează-ți două poziții care înaintează printr-un vector ordonat; poziția interioară nu revine niciodată la început. Dacă fiecare poziție poate avansa cel mult n ori, totalul avansurilor este cel mult două ori n.

Argumentul urmărește evoluția variabilelor pe întregul algoritm. Dacă poziția interioară se resetează la fiecare iterație exterioară, justificarea nu mai este valabilă. De aceea, trebuie citită inițializarea, nu doar indentarea codului.

Acest tip de control este potrivit pentru învățarea prin înțelegere: marchează de câte ori poate trece fiecare indice prin aceeași poziție. Dacă spui „o singură dată”, arată instrucțiunea care împiedică revenirea.

Timpul și memoria sunt două întrebări diferite

Un algoritm care citește n valori dintr-un fișier și păstrează numai cele mai mari două valori distincte are timp liniar și memorie suplimentară constantă, dacă numerele au dimensiune fixă în modelul folosit. Nu trebuie să memoreze întregul fișier.

Dacă stochezi toate valorile într-un vector cu n poziții, memoria pentru acel vector crește liniar. Timpul de citire rămâne liniar, dar proprietatea memoriei s-a schimbat. Precizează dacă discuți memoria totală sau memoria suplimentară față de datele deja memorate.

Un tablou de frecvență cu o sută de poziții fixe ocupă memorie constantă în raport cu n. Un tablou cu câte o poziție pentru fiecare valoare până la un prag M ocupă memorie proporțională cu M. „Folosesc un singur tablou” nu înseamnă automat memorie constantă.

Exerciții cu justificări scurte

1. O buclă parcurge n elemente și încă una parcurge trei elemente. Totalul operațiilor este n+3, cu ordin liniar. Numărul fix de pași nu schimbă dependența principală de n.
2. Pentru fiecare dintre n linii parcurgi m coloane. Sunt n·m operații. Dacă matricea este pătratică și m=n, rezultatul devine n².
3. O buclă împarte repetat valoarea 31 la doi, folosind împărțirea întreagă. Valorile pozitive sunt 31, 15, 7, 3 și 1, deci cinci pași. Nu există treizeci și unu de iterații.
4. Păstrezi minimul curent în timp ce citești un milion de valori. Faci o parcurgere și folosești un număr fix de variabile. Volumul datelor nu te obligă să păstrezi un milion de numere simultan.

Întrebări frecvente

O soluție mai scurtă în cod este mai eficientă?

Nu neapărat. O singură expresie poate ascunde o parcurgere sau o sortare. Evaluează operațiile efectuate și dimensiunea datelor, nu numărul liniilor din program.

Pot ignora cazul cel mai nefavorabil?

Numai dacă cerința cere explicit alt tip de analiză. O oprire timpurie poate face anumite intrări rapide, dar trebuie să verifici și intrarea care obligă algoritmul să execute toate iterațiile posibile.

Cum redactez justificarea la BAC?

Numește dimensiunea, operația repetată, numărul parcurgerilor și variabilele memorate. Exersează pe cerințe din arhiva BAC, apoi compară explicația cu baremul. Pentru feedback punctual, poți consulta anunțuri de meditații la informatică și prezenta chiar algoritmul pentru care nu poți justifica eficiența.