Ce vei învăța astăzi?
Doi algoritmi pot rezolva aceeași problemă, dar unul poate fi de mii de ori mai rapid. Astăzi înveți să măsori și să compari eficiența.
Dicționar: Eficiență ↔ C++
| Concept matematic | Cum se citește | În C++ | Observație |
|---|---|---|---|
| Eficiență = nr. operații | „cât de repede" | int pasi = 0; pasi++; | contor de pași |
| O(1) — constant | „un singur pas" | int x = v[5]; | acces direct, fără buclă |
| O(log n) — logaritmic | „împarte la 2 repetat" | while(st <= dr) { mij=(st+dr)/2; } | căutare binară, Euclid |
| O(n) — liniar | „parcurge tot" | for(int i=0; i<n; i++) | un singur for |
| O(n) — pătratic | „for în for" | for(i) for(j) ... | Bubble Sort, brut force |
| O(2ⁿ) — exponențial | „se dublează" | fib(n-1) + fib(n-2) | recursie fără memo = groaznic |
| clock() — cronometru CPU | „timp procesor" | clock_t t = clock(); | CLOCKS_PER_SEC pt secunde |
| log₂(n) ≈ 20 pt n=10⁶ | „logaritm baza 2" | (int)log2(n) | include <cmath> |
Ce este eficiența?
Analogie: Drumul spre școală
Poți ajunge la școală pe drumul lung (30 min) sau pe scurtătură (10 min). Ambele te duc la destinație, dar scurtătura e de 3 ori mai eficientă. La fel și algoritmii: doi pot da același rezultat, dar unul face treaba mult mai repede!
Eficiența unui algoritm măsoară cât de repede rezolvă o problemă și câtă memorie folosește. Măsurăm în număr de operații, nu în secunde (care depind de calculator).
| Măsurăm | Ce înseamnă | Vrem să fie | Exemplu |
|---|---|---|---|
| Timp | Câți pași / operații face | Cât mai mic | CMMDC: 20 vs 999.999 pași |
| Memorie | Câte variabile / vectori | Cât mai mică | 3 variabile vs vector de 1M |
| Nr. comparații | De câte ori verificăm | Cât mai mic | Căutare: 20 vs 1.000.000 |
Clase de complexitate (Big-O simplifcat)
Notația Big-O descrie cum crește timpul de execuție când crește dimensiunea datelor (n). Nu ne interesează constanta, ci „forma" creșterii.
| Complexitate | Nume | n=10 | n=1.000 | n=1.000.000 | Exemplu algoritm |
|---|---|---|---|---|---|
| O(1) | Constant | 1 | 1 | 1 | Acces v[i] |
| O(log n) | Logaritmic | 3 | 10 | 20 | Căutare binară |
| O(n) | Liniar | 10 | 1.000 | 1.000.000 | Căutare secvențială |
| O(n) | Pătratic | 100 | 1.000.000 | 10 | Bubble sort |
| O(2ⁿ) | Exponențial | 1.024 | ~10⁰⁰ | ∞ | Subset sum |
Regulă simplă
1 for simplu → O(n) | 2 for-uri imbricale → O(n) | Împărțim la jumătate → O(log n) | Fără bucle → O(1)
Exemplul 1: CMMDC - Euclid vs. For
Comparație vizuală: CMMDC(1.000.000, 999.999)
Metoda for (O(n)):
Algoritmul Euclid (O(log n)):
Euclid este de ~50.000 ori mai rapid!
#include <iostream>
#include <ctime>
using namespace std;
int cmmdc_for(int a, int b) { // O(min(a,b))
int m = min(a, b);
for (int d = m; d >= 1; d--)
if (a % d == 0 && b % d == 0)
return d;
return 1;
}
int cmmdc_euclid(int a, int b) { // O(log(min(a,b)))
while (b != 0) {
int r = a % b;
a = b; b = r;
}
return a;
}
int main() {
int a = 1000000, b = 999983;
clock_t start1 = clock();
int r1 = cmmdc_for(a, b);
clock_t end1 = clock();
double t1 = double(end1 - start1) / CLOCKS_PER_SEC;
clock_t start2 = clock();
int r2 = cmmdc_euclid(a, b);
clock_t end2 = clock();
double t2 = double(end2 - start2) / CLOCKS_PER_SEC;
cout << "For: " << r1 << " in " << t1 << "s" << endl;
cout << "Euclid: " << r2 << " in " << t2 << "s" << endl;
return 0;
}
Trace Euclid: CMMDC(48, 18)
| Pas | a | b | r = a % b | Acțiune |
|---|---|---|---|---|
| 1 | 48 | 18 | 12 | a←18, b←12 |
| 2 | 18 | 12 | 6 | a←12, b←6 |
| 3 | 12 | 6 | 0 | a←6, b←0 → STOP |
Rezultat: CMMDC = 6 (doar 3 pași! For-ul ar face 18 pași.)
clock() vs cronometru: clock() măsoară timpul procesorului, nu timpul real. Pentru numere mici, ambele metode par instant. Diferența se vede la numere mari (>100.000).
Exemplul 2: Căutare secvențială vs. binară
Secvențială O(n): verifici fiecare element pe rând | Binară O(log n): împarți la jumătate (vectorul TREBUIE sortat)
| Nr. elemente (n) | Secvențială (max) | Binară (max) | Câte ori mai rapid? |
|---|---|---|---|
| 10 | 10 | 4 | 2.5× |
| 100 | 100 | 7 | 14× |
| 1.000 | 1.000 | 10 | 100× |
| 1.000.000 | 1.000.000 | 20 | 50.000× |
int cautareBinara(int v[], int n, int x, int &pasi) {
int st = 0, dr = n - 1;
pasi = 0;
while (st <= dr) {
pasi++;
int mij = (st + dr) / 2;
if (v[mij] == x) return mij; // gasit
else if (v[mij] < x) st = mij + 1; // dreapta
else dr = mij - 1; // stanga
}
return -1; // nu exista
}
// Exemplu: v = {2,5,8,11,14,17,20,23,26,29}, x=17
// Pas 1: mij=4, v[4]=14 < 17 -> st=5
// Pas 2: mij=7, v[7]=23 > 17 -> dr=6
// Pas 3: mij=5, v[5]=17 == 17 -> GASIT! (3 pasi)
Trace: Căutare binară x=17 în {2,5,8,11,14,17,20,23,26,29}
| Pas | st | dr | mij | v[mij] | Comparație | Acțiune |
|---|---|---|---|---|---|---|
| 1 | 0 | 9 | 4 | 14 | 14 < 17 | st ← 5 |
| 2 | 5 | 9 | 7 | 23 | 23 > 17 | dr ← 6 |
| 3 | 5 | 6 | 5 | 17 | 17 = 17 | GĂSIT la poz 5! |
3 pași din 10 elemente (secvențiala ar fi făcut 6).
Când folosesc binara? Doar pe date sortate. Dacă datele nu sunt sortate, fie le sortezi întâi (dar sortarea costă O(n log n)), fie folosești secvențiala.
Verificare cunoștințe
1. Un algoritm cu 10 pași vs. unul cu 10.000 pași:
2. Câți pași face căutarea binară în 1.000.000 elemente?
3. Căutarea binară funcționează pe vectori:
4. Ce complexitate are un for de la 1 la n?
5. Două for-uri imbricate (for i + for j) dau:
6. Euclid pentru CMMDC are complexitatea:
Extensie: cum recunoști rapid complexitatea
Nu trebuie să numeri fiecare instrucțiune. Pentru estimarea eficienței, cauți forma dominantă a algoritmului.
| Model de cod | Complexitate | Exemplu |
|---|---|---|
| fără bucle | O(1) | calculezi o formulă |
| o buclă până la n | O(n) | căutare secvențială |
| două bucle imbricate | O(n^2) | compari toate perechile |
| împarți problema la 2 | O(log n) | căutare binară |
Regulă practică: pentru n mare, termenul care crește cel mai repede domină. De aceea O(n^2) devine rapid mult mai lent decât O(n log n) sau O(n).
Întrebări frecvente (FAQ)
Timpul în secunde depinde de calculator: același algoritm rulează în 1s pe un PC vechi și 0.01s pe unul nou. Numărul de operații e independent de hardware.
Pentru n mare, da. Dar pentru n=5, diferența e neglijabilă (5 vs 25 operații). Big-O contează la scale mari. Pentru probleme mici, chiar și O(n) e instant.
Binară: dacă datele sunt DEJA sortate sau le sortezi o singură dată și cauți de mai multe ori. Secvențială: date nesortate, o singură căutare, sau liste mici.
Da, clock() are rezoluție limitată. Pentru funcții foarte rapide, rulează-le de 1.000.000 de ori într-o buclă și măsoară totalul divid la 1M.
PbInfo - Masurare cu clock
Timp de executie
Enunț:
Cerință: Se citeste n. Calculeaza suma 1+2+...+n si afiseaza timpul aproximativ de executie.
Date de intrare:
n.
Date de ieșire:
Suma si timpul.
Exemplu:
Intrare:
100000
Ieșire:
5000050000 timp
Explicație: Timpul depinde de calculator.
Cum gândim soluția:
- Pornim cronometrul cu clock().
- Rulam bucla.
- Oprim cronometrul si calculam diferenta.
Tip: Timpul este orientativ, nu o valoare fixa. clock() masoara aproximativ timpul consumat de program pe calculatorul tau, deci rezultatul poate diferi de la un PC la altul.
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
#include <ctime>
using namespace std;
int main() {
int n;
cin >> n;
clock_t start = clock();
long long s = 0;
for (int i = 1; i <= n; i++)
s += i;
clock_t stop = clock();
cout << s << " " << double(stop - start) / CLOCKS_PER_SEC;
}
PbInfo - Cautare secventiala
Comparatii
Enunț:
Cerință: Se citeste n, apoi n numere si x. Afiseaza pozitia lui x sau -1.
Date de intrare:
n, sirul, x.
Date de ieșire:
Pozitia sau -1.
Exemplu:
Intrare:
5 4 8 2 9 1 2
Ieșire:
3
Explicație: 2 se afla pe pozitia 3.
Cum gândim soluția:
- Parcurgem sirul de la stanga la dreapta.
- Daca gasim x, memoram pozitia.
- Daca nu gasim, afisam -1.
Tip: Cautarea secventiala nu cere sir sortat.
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int main() {
int n, x, poz = -1;
cin >> n;
int v[1001];
for (int i = 1; i <= n; i++)
cin >> v[i];
cin >> x;
for (int i = 1; i <= n; i++) {
if (v[i] == x && poz == -1) {
poz = i; // salvam prima pozitie gasita
}
}
cout << poz;
}
PbInfo - Cautare binara
Algoritm eficient
Enunț:
Cerință: Se citeste un sir sortat si x. Afiseaza DA daca x apare in sir.
Date de intrare:
n, sir sortat, x.
Date de ieșire:
DA sau NU.
Exemplu:
Intrare:
5 1 3 5 7 9 7
Ieșire:
DA
Explicație: 7 se gaseste prin injumatatiri succesive.
Cum gândim soluția:
- Setam stanga=1 si dreapta=n.
- Calculam mijlocul.
- Micsoram intervalul dupa comparatie.
Tip: Cautarea binara cere sir sortat.
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int main() {
int n, x, v[1001];
cin >> n;
for (int i = 1; i <= n; i++)
cin >> v[i];
cin >> x;
int st = 1, dr = n;
bool ok = false;
while (st <= dr) {
int m = (st + dr) / 2;
if (v[m] == x) {
ok = true;
break;
}
if (v[m] < x)
st = m + 1;
else
dr = m - 1;
}
cout << (ok?"DA":"NU");
}
Exercițiul Practic: Eficiență algoritmică
Compară metode de rezolvare prin numărarea pașilor, căutare secvențială/binară și măsurare practică. Important: timpul măsurat poate varia, dar numărul de pași arată clar diferența dintre algoritmi.
Când folosim fiecare căutare? Căutarea secvențială merge pe orice șir. Căutarea binară este mult mai rapidă, dar funcționează corect doar dacă șirul este deja sortat.
Sarcina 1: Contorizează pașii CMMDC
Pași de rezolvare
- Adaugă parametru
int &pasi(referință) la ambele funcții CMMDC - Inițializează
pasi = 0;la început - Adaugă
pasi++;în interiorul buclei (for / while) - Testează cu 5 perechi diferite (numere mari pentru diferență vizibilă)
- Afișează tabel: a, b, pași_for, pași_euclid, raport
Modifică ambele funcții CMMDC să numere pașii. Afișează comparația pentru 5 perechi de numere.
De ce funcționează? Parametrul int &pasi este o referință — modificările se reflectă în main(). Incrementăm pasi++ la fiecare iterație, astfel numărăm exact câte bucle face algoritmul. Euclid are ~log₂(min(a,b)) pași, iar for-ul are ~min(a,b) pași.
int cmmdc_for(int a, int b, int &pasi){ // O(min(a,b)) — parcurge de la min descrescător
pasi=0; int m=min(a,b); // inițializare contor + limita
for(int d=m; d>=1; d--){ // parcurgem descrescător
pasi++; // numaram fiecare iteratie
if(a%d==0&&b%d==0) return d; // gasit CMMDC
}
return 1; // fallback: CMMDC = 1
}
int cmmdc_euclid(int a, int b, int &pasi){ // O(log min(a,b))
pasi=0;
while(b!=0){ // cat timp b nenul
int r=a%b; a=b; b=r; // reste succesive
pasi++; // numaram iteratia
}
return a; // CMMDC ramas in a
}
// Test: (48,18) -> For:18 pasi, Euclid:3 pasi
// (1000000,999999) -> For:~999999, Euclid:~20
Sarcina 2: Căutare comparativă
Pași de rezolvare
- Generează vector sortat:
v[i] = i * 3;(0, 3, 6, ..., 297) - Alege un element de căutat (ex:
x = 150) - Secvențială: for simplu cu contor
c1++ - Binară: while cu st/dr/mij și contor
c2++ - Afișează ambele contoare; binara ar trebui ≈ 7 pași
Generează un vector sortat de 100 elemente. Caută un element cu ambele metode. Afișează nr. comparații.
De ce funcționează? Vectorul sortat v[i] = i*3 permite ambele metode. Secvențiala parcurge element cu element (51 pași pentru x=150), iar binara înjumătățește intervalul de fiecare dată (≈7 pași). Diferența e clară: 51 vs 7.
int v[100]; // vector sortat de 100 elemente
for(int i=0; i<100; i++) v[i] = i*3; // generare: 0,3,6,...,297
int x = 150; // valoare de cautat
// === Cautare secventiala: O(n) ===
int c1=0;
for(int i=0; i<100; i++){
c1++; // numaram fiecare comparatie
if(v[i]==x) break; // gasit → oprire
}
// === Cautare binara: O(log n) ===
int c2=0, st=0, dr=99; // limitele intervalului
while(st<=dr){
c2++; // numaram fiecare pas
int m=(st+dr)/2; // mijlocul intervalului
if(v[m]==x) break; // gasit
else if(v[m]<x) st=m+1; // cauta in dreapta
else dr=m-1; // cauta in stanga
}
cout << "Secventiala: " << c1 << " | Binara: " << c2; // 51 vs ~7