BAC informatică: cum explici eficiența algoritmului
Argumentează timpul și memoria unei soluții cu operațiile pe care le execută. Vezi un exemplu de parcurgere unică și formulări care trebuie evitate.
În acest material
O explicație a eficienței trebuie să descrie ce face algoritmul și de câte ori, raportat la dimensiunea datelor. „Este eficient deoarece folosește un for” nu este suficient: un for poate executa un număr mare de operații, iar două bucle una după alta pot avea tot timp liniar.
Definește ce reprezintă n
Dacă citești n numere, n este numărul valorilor, nu valoarea maximă dintre ele. Dacă prelucrezi cifrele unui singur număr, dimensiunea relevantă poate fi numărul de cifre. Dacă ai o matrice n×m, trebuie să explici dependența de ambele dimensiuni.
Această precizare previne afirmații precum „O(n)” pentru o soluție în care n nu apare nicăieri definit. Folosește notațiile din enunț sau explică imediat orice notație nouă.
Două parcurgeri succesive de câte n pași costă 2n; două parcurgeri complete imbricate examinează n ori n perechi.Mărește schema ↗
Exemplu: numărul aparițiilor maximului
O soluție poate citi fiecare valoare o singură dată și păstra maximul curent și numărul lui de apariții. Când apare un maxim nou, numărul devine 1. Când apare o valoare egală cu maximul, crește cu 1. O valoare mai mică nu schimbă starea.
Argumentul de timp este concret: fiecare dintre cele n valori este citită o dată și provoacă un număr constant de comparații și atribuiri. Timpul este O(n). Argumentul de memorie este separat: păstrăm doar câteva variabile, indiferent de n, deci memoria auxiliară este O(1), dacă nu memorăm întregul șir.
Două bucle nu înseamnă automat O(n²)
O parcurgere de n pași urmată de alta de n pași costă aproximativ 2n operații de același ordin, deci O(n). Două bucle imbricate care parcurg fiecare întregul șir pot produce n² perechi. Diferența este multiplicarea lucrului, nu numărul de cuvinte for din cod.
La o buclă în care variabila se dublează, numărul de pași nu este n. Explică de câte ori se poate dubla înainte să treacă limita. La căutarea binară, intervalul de căutare se înjumătățește, motivul timpului logaritmic.
Separă memoria datelor de memoria suplimentară
Dacă programul memorează un vector cu n elemente și apoi folosește trei variabile, memoria totală nu este O(1). Poți spune că starea auxiliară a prelucrării este constantă, iar vectorul ocupă O(n). Dacă cerința permite procesarea directă la citire, explică de ce nu ai nevoie de valorile anterioare.
O soluție pe care o numești „fără vector” trebuie să fie corectă și pentru operațiile ulterioare. Dacă trebuie afișate valorile în ordine inversă, simpla agregare la citire nu mai păstrează informația necesară.
Cum verifici formularea la antrenament
Scrie explicația înainte să consulți baremul, apoi compar-o cu cerința și baremul variantei concrete. Acest articol oferă o metodă de argumentare, nu promite un punctaj și nu înlocuiește documentele oficiale. Unele cerințe urmăresc eficiența în timp, altele și memoria.
Folosește lecția despre complexitate, maxime și numărări și arhiva de subiecte cu bareme pentru exerciții în care poți verifica exact ce s-a cerut.
Întrebări frecvente
Cum explic eficiența unui algoritm la informatică?
Definește dimensiunea intrării, arată de câte ori sunt procesate datele și precizează memoria folosită. De exemplu, o singură parcurgere cu un număr constant de operații pe element are timp O(n).
Două bucle for înseamnă întotdeauna O(n²)?
Nu. Două bucle consecutive de câte n pași au timp O(n). Două bucle imbricate care execută fiecare n pași pot avea O(n²); trebuie numărate execuțiile reale, nu instrucțiunile for.
Care este diferența dintre memoria totală și memoria auxiliară?
Memoria totală include și datele stocate ale intrării. Memoria auxiliară este spațiul suplimentar folosit de algoritm. O parcurgere poate avea stare auxiliară O(1), deși tabloul citit ocupă O(n).