Ce înseamnă „algoritm eficient” la bacalaureatul de informatică?
Un algoritm care folosește timp și memorie pe măsura problemei. De obicei, o singură parcurgere a datelor, fără să rețină în memorie ce nu îi trebuie.
La problema cu fișier din Subiectul III, baremul dă puncte separate pentru eficiență: în timp (numărul de pași) și în memorie (cât reține programul deodată).
Ce înseamnă concret:
- Timp. Dacă fișierul are un milion de numere, o singură parcurgere este eficientă. Două bucle imbricate care compară fiecare număr cu fiecare (un milion de milioane de pași) nu sunt. Testul de primalitate se face până la radical din
n, nu până lan. - Memorie. Dacă poți calcula rezultatul pe măsură ce citești (o sumă, un maxim, un contor), nu reține toate valorile într-un vector. Vectorul se justifică doar când ai nevoie de valori după ce le-ai citit pe toate.
La cerința a) descrii în cuvinte ce face algoritmul și de ce este eficient: „parcurg fișierul o singură dată și rețin doar ultimele două valori, deci memoria nu depinde de numărul de valori”. Fără justificare, descrierea nu ia punctele.
Lecția Ce este un algoritm are exemplul cu numerele prime, iar cea despre vectori îți spune când ai nevoie de unul.
Lecția care merge mai departe: Tablouri unidimensionale