Ce vei învăța astăzi?
După această lecție vei putea compara algoritmi pe baza numărului de operații și vei ști să alegi varianta eficientă pentru o problemă.
Eficiența algoritmilor: timp și spațiu
Definiție: Eficiența unui algoritm ne arată câte resurse consumă atunci când este executat. Cele două resurse importante sunt timpul de executare (cât timp durează) și spațiul de memorie (câtă memorie ocupă).
Vrem, pe cât posibil, algoritmi care execută puține operații și care folosesc puțină memorie.
Analogie: două trasee către școală
Imaginează-ți două trasee de acasă până la școală: unul scurt și unul lung. Ambele te duc la aceeași școală (același rezultat), dar traseul scurt te duce mult mai repede și consumă mai puțină energie. Exact așa este și cu algoritmii: doi algoritmi pot rezolva aceeași problemă, dar unul execută mai puține operații și este mai eficient.
Numărul de operații efectuate de algoritm
Câtă memorie ocupă datele folosite
Puține operații, puțină memorie, rezultat corect
De reținut: eficiența nu înseamnă un singur lucru. Un algoritm poate fi rapid, dar să ocupe multă memorie. Comparăm algoritmi analizând cu atenție ambele aspecte.
Notația O (ordinul de complexitate)
Definiție: Notația O ne spune cum crește numărul de operații ale unui algoritm atunci când crește numărul de date de intrare n. Scriem O(...) și citim „ordinul de complexitate".
Cele mai frecvente complexități sunt O(1), O(log n), O(n) și O(n^2).
Complexitățile pe care le vei întâlni
| Algoritm | Număr de operații pentru n = 1000 | Ordin de complexitate |
|---|---|---|
| Acces direct la o valoare (formulă) | 1 | O(1) |
| Căutare binară într-o listă sortată | aproximativ 10 | O(log n) |
| Căutare secvențială (verificarea elementelor unul câte unul, în ordine) într-o listă | până la 1000 | O(n) |
| Comparare a două liste cu bucle duble | până la 1.000.000 | O(n^2) |
Exemplu complet: suma 1 + 2 + ... + n
Vrem să calculăm suma primelor n numere naturale. Avem două variante. Prima folosește o formulă matematică și execută un număr constant de operații, indiferent de n:
n = int(input()) suma = n * (n + 1) // 2 print(suma)
A doua variantă folosește o buclă for care adună pe rând fiecare număr. Pentru n = 1000 execută 1000 de operații:
n = int(input())
suma = 0
for i in range(1, n + 1):
suma += i
print(suma)
Observă: ambele variante dau același rezultat, dar varianta 1 execută o singură operație, indiferent de n. Pentru n foarte mare, diferența de viteză devine uriașă.
Compararea algoritmilor: numărarea operațiilor
Pentru a compara doi algoritmi, numărăm operațiile pe care le execută fiecare pentru aceeași intrare. Algoritmul cu mai puține operații este, de regulă, cel mai eficient.
Pentru o listă cu n = 5 elemente, o parcurgere cu o buclă for execută corpul buclei de 5 ori:
Exemplu: căutarea secvențială într-o listă (O(n))
Căutarea secvențială verifică, unul câte unul, toate elementele unei liste până găsește valoarea căutată. În cel mai rău caz, când valoarea nu există, parcurgem întreaga listă. De aceea complexitatea este O(n).
v = list(map(int, input().split()))
x = int(input())
gasit = False
for element in v:
if element == x:
gasit = True
if gasit:
print("DA")
else:
print("NU")
Observă: folosim un indicator gasit care pornește cu valoarea False și devine True atunci când găsim valoarea căutată. La final afișăm DA sau NU.
Exercițiu de completare - complexități
Completează enunțul despre complexități cu răspunsurile potrivite:
Un algoritm care execută un număr constant de operații, indiferent de datele de intrare, are complexitatea ______. Un algoritm care parcurge o singură dată o listă cu n elemente are complexitatea ______. Pentru o listă cu 1000 de elemente, o căutare secvențială efectuează, în cel mai rău caz, ______ de operații.
Bancă de cuvinte:
Exercițiu de completare - suma
Completează enunțul despre suma primelor n numere:
Suma primelor n numere naturale se calculează cu formula ______, care execută un număr constant de operații, deci are complexitatea ______. Varianta cu bucla for efectuează n operații de adunare, deci are complexitatea ______.
Bancă de cuvinte:
Test de înțelegere
Test rapid - eficiență și notația O:
1. Ce complexitate are un algoritm care execută un număr constant de operații, indiferent de mărimea datelor?
2. Pentru n = 1000, câte operații efectuează, în cel mai rău caz, o căutare secvențială într-o listă cu n elemente?
3. Ce complexitate are varianta cu bucla for pentru suma 1 + 2 + ... + n?
O(n) și O(n^2) nu se vede, dar pe date mari devine uriașă.Aprofundare
De ce ignorăm constantele în notația O? Notația O descrie cum crește numărul de operații, nu câte operații sunt exact. De aceea, un algoritm cu 3n operații și unul cu 100n operații au amândouă complexitatea O(n): când n crește, ambele cresc proporțional. Constantele contează practic, dar nu schimbă forma de creștere. Tot așa, 2n + 5 devine pur și simplu O(n), iar n^2 + n devine O(n^2), pentru că termenul dominant (termenul care crește cel mai repede) este n^2.
Când n este mic, eficiența pare irelevantă. Pentru n = 10, un algoritm O(n^2) execută 100 de operații - instantaneu. Diferența devine dramatică doar la valori mari: pentru n = 1.000.000, O(n) execută un milion de operații, iar O(n^2) execută un miliard de miliarde - adică o diferență de un milion de ori. Exact de aceea platformele de evaluare impun restricții mari la datele de intrare.
Cazuri particulare de complexitate. Există și complexități mai rare în liceu: O(n log n) - sortarea eficientă, sau O(2^n) - algoritmi exponențiali, de evitat. De asemenea, o buclă for imbricată în altă buclă for are O(n^2), iar trei bucle imbricate au O(n^3). Regula practică: fiecare buclă care parcurge n adaugă un factor n.
PbInfo - Suma primelor n numere
Enunț:
Cerință: Se citește numărul natural n. Să se afișeze suma primelor n numere naturale: 1 + 2 + ... + n.
Date de intrare:
Programul citește de la tastatură numărul n.
Date de ieșire:
Programul va afișa pe ecran suma primelor n numere naturale.
Restricții și precizări:
n este un număr natural, iar rezultatul se poate încadra pe 64 de biți.
Exemplu:
Intrare:
5
Ieșire:
15
Cum gândim soluția:
- Citim numărul n cu
int(input()) - Aplicăm formula
n * (n + 1) // 2, o singură operație - Afișăm rezultatul cu
print()
Scrie soluția în Python:
Soluție corectă:
n = int(input()) suma = n * (n + 1) // 2 print(suma)
Ce învățăm: folosim formula pentru suma primelor n numere naturale. Programul execută un număr constant de operații, indiferent de valoarea lui n, deci are complexitatea O(1).
PbInfo - Căutarea unui element
Enunț:
Cerință: Se citește o listă de numere naturale și apoi un număr x. Să se verifice dacă x se află în listă.
Date de intrare:
Programul citește de la tastatură numerele din listă, separate prin spații, urmate de numărul x.
Date de ieșire:
Programul va afișa pe ecran DA dacă x se găsește în listă, altfel NU.
Restricții și precizări:
Lista conține cel mult 1.000.000 de numere naturale.
Exemplu:
Intrare:
3 8 5 12 9 8
Ieșire:
DA
Cum gândim soluția:
- Citim lista într-o singură linie și o transformăm cu
split()șimap(int, ...) - Citim valoarea x căutată
- Parcurgem lista cu o buclă
forși folosim indicatorulgasit - Afișăm DA sau NU
Scrie soluția în Python:
Soluție corectă:
v = list(map(int, input().split()))
x = int(input())
gasit = False
for element in v:
if element == x:
gasit = True
if gasit:
print("DA")
else:
print("NU")
Ce învățăm: căutarea secvențială parcurge lista element cu element. În cel mai rău caz parcurgem toate cele n elemente, deci complexitatea este O(n).
Exercițiul Practic: Compararea eficienței algoritmilor
Sarcini de lucru
Compară algoritmi prin numărul de operații și scrie un program care numără operațiile unei bucle
Sarcina 1: Alege varianta eficientă
Cerință: Pentru calculul sumei 1 + 2 + ... + n, scrie care dintre cele două variante (formula sau bucla for) este mai eficientă și explică de ce.
Soluție pentru Sarcina 1:
Răspuns corect:
Varianta cu formula n * (n + 1) // 2 este mai eficientă. Ea execută un număr constant de operații (o singură formulă), indiferent de valoarea lui n, deci are complexitatea O(1). Varianta cu bucla for execută n operații de adunare, deci complexitatea O(n). Pentru n mare, formula este mult mai rapidă.
Verifică: pentru n = 1000, varianta 1 execută 1 operație, iar varianta 2 execută 1000 de operații.
Sarcina 2: Numără operațiile unei bucle
Cerință: Scrie un program care citește n și afișează de câte ori se execută corpul unei bucle for cu range(n).
Soluție pentru Sarcina 2:
n = int(input())
numar_operatii = 0
for i in range(n):
numar_operatii += 1
print(numar_operatii)
Verifică: bucla for cu range(n) execută corpul de n ori. Programul afișează valoarea n, confirmând complexitatea O(n) a buclei.
Scrie pe caiet - De reținut
Titlul lecției
Ora 10: Eficiența algoritmilor și notația O
Definiția lecției
Eficiența unui algoritm ne arată câte resurse consumă atunci când este executat, cele două resurse importante fiind timpul de executare și spațiul de memorie. Pentru a compara algoritmi, numărăm operațiile pe care le execută pentru aceeași intrare, iar cel cu mai puține operații este, de regulă, cel mai eficient. Notația O descrie cum crește numărul de operații atunci când crește numărul de date de intrare n: O(1) înseamnă un număr constant de operații, O(log n) o creștere foarte lentă, O(n) o creștere proporțională cu n, iar O(n^2) o creștere rapidă, ca la două bucle imbricate. De exemplu, suma primelor n numere se poate calcula cu formula n * (n + 1) / 2, într-o singură operație (O(1)), sau cu o buclă care adună fiecare număr (O(n)); pentru n mare, diferența de viteză devine uriașă, exact ca între un traseu scurt și unul lung către aceeași destinație.
Definiții esențiale
- Eficiența unui algoritm - câte resurse consumă: timp de executare și spațiu de memorie.
- Notația O - descrie cum crește numărul de operații când crește numărul de date n.
- O(1) - număr constant de operații, independent de n (o formulă).
- O(n) - operații proporționale cu n (o parcurgere a listei).
- O(n^2) - operații proporționale cu n^2 (două bucle imbricate).
- Căutarea secvențială - verifică elementele unul câte unul, complexitate O(n).
Algoritmul cheie - pseudocod
Algoritmul cheie - cod Python
n = int(input()) suma = n * (n + 1) // 2 print(suma)
Greșeli comune de evitat
- Alegerea variantei cu buclă când există o formulă: bucla are O(n), formula are O(1).
- Numărarea greșită a operațiilor unei bucle imbricate - două bucle dau O(n^2), nu O(2n).
- Confuzia dintre O(n) și O(log n): O(log n) crește mult mai lent.
- Ignorarea restricțiilor problemei: pentru n mare, un algoritm ineficient nu se termină în timp util.
Sfaturi practice și trucuri
- Înainte de a scrie codul, gândește-te dacă există o formulă matematică care evită buclele.
- Numără buclele: fiecare buclă independentă de n adaugă un factor n la complexitate.
- Compară algoritmi prin numărul de operații pentru aceeași valoare a lui n.
- Pentru n mare, alege întotdeauna varianta cu cea mai mică complexitate.
Exemplu practic
O platformă de evaluare are o listă cu un milion de utilizatori și primește o cerere de căutare a unui anumit cont. Dacă programul verifică conturile unul câte unul, face un milion de operații (O(n)); dacă lista este sortată și folosim căutarea binară, ajungem la rezultat în aproximativ douăzeci de pași (O(log n)). Alegerea metodei eficiente face diferența dintre un răspuns instantaneu și unul care durează:
n = int(input()) suma = n * (n + 1) // 2 print(suma)