Ce facem astăzi?
Analizăm probleme concrete cu 2 soluții diferite. Tu decizi care e mai eficientă și de ce!
Dicționar: Analiză comparativă ↔ C++
| Concept | Cum se citește | În C++ | Observație |
|---|---|---|---|
| n / 2 — formulă directă | „n supra 2" | int cont = n / 2; | O(1) — un singur pas |
| √n — radical | „rădăcina pătrată din n" | d * d <= n | evită sqrt() — mai rapid |
| a^n — ridicare la putere | „a la puterea n" | rez *= baza; | sucesiv O(n) sau rapid O(log n) |
| Fibonacci recursiv vs iterativ | „al n-lea termen" | fib(n-1)+fib(n-2) vs for | recursiv O(2ⁿ) vs iterativ O(n) |
| Exponențiere rapidă | „baza la exponent prin înjumătățire" | while(exp > 0) { exp /= 2; baza *= baza; } | log₂(n) pași |
| Overflow | „depășire de tip" | long long rez; | max ≈ 9.2 × 10⁸ |
| Contor de pași | „numărătoare operații" | int pasi = 0; pasi++; | măsoară eficiența |
Analogie: Cutia de scule
Imaginează-ți că trebuie să înșurubezi un șurub:
Ai două opțiuni: o șurubelniță manuală (funcționează, dar lent) sau un bormaș electric (rapid și eficient). Ambele fac treaba, dar bormașul termină de 100 de ori mai repede.
La fel în programare: două algoritmi pot rezolva aceeași problemă, dar diferența de viteză poate fi enormă. Un programator bun alege întotdeauna „bormașul" — algoritmul mai eficient.
Problema 1: Numărare numere pare
Enunț: Câte numere pare sunt de la 1 la n?
Metoda A: Parcurgere cu for
int cont = 0;
for (int i = 1; i <= n; i++)
if (i % 2 == 0) cont++;
// n pași
Metoda B: Formulă directă
int cont = n / 2; // 1 singur pas!
| n | Metoda A (pași) | Metoda B (pași) | Câștig |
|---|---|---|---|
| 10 | 10 | 1 | 10x |
| 1.000 | 1.000 | 1 | 1.000x |
| 1.000.000 | 1.000.000 | 1 | 1.000.000x |
Lecție: Când există o formulă matematică directă, aceasta este întotdeauna mai eficientă decât parcurgerea.
Problema 2: Verificare număr prim
Enunț: Este n prim?
Metoda A: Verificăm toți divizorii de la 2 la n-1
bool prim = true;
for (int d = 2; d < n; d++)
if (n % d == 0) { prim = false; break; }
// Până la n-1 pași
Metoda B: Verificăm doar până la √n
bool prim = (n >= 2);
for (int d = 2; d * d <= n; d++)
if (n % d == 0) { prim = false; break; }
// Până la √n pași
| n | Metoda A (max pași) | Metoda B (max pași) |
|---|---|---|
| 100 | 98 | 10 |
| 10.000 | 9.998 | 100 |
| 1.000.000 | 999.998 | 1.000 |
Problema 3: Calculul puterii a^n
Metoda A: Înmulțiri succesive
long long rez = 1;
for (int i = 0; i < n; i++)
rez *= a;
// n pași
Metoda B: Ridicare rapidă la putere
long long rez = 1, baza = a;
int exp = n;
while (exp > 0) {
if (exp % 2 == 1) rez *= baza;
baza *= baza;
exp /= 2;
}
// log₂(n) pași!
Exemplu: 2^16
Metoda A: 16 înmulțiri
Metoda B: 2→4→8→16→32→64→128→256→...→65536 = doar 4 pași!
Trace: Exponențiere rapidă 2^10
| Pas | exp | baza | rez | exp%2 | Acțiune |
|---|---|---|---|---|---|
| 0 | 10 | 2 | 1 | — | inițializare |
| 1 | 10 | 2→4 | 1 | 0 (par) | baza=4, exp=5 |
| 2 | 5 | 4→16 | 1×4=4 | 1 (impar) | rez×=4, baza=16, exp=2 |
| 3 | 2 | 16→256 | 4 | 0 (par) | baza=256, exp=1 |
| 4 | 1 | 256→... | 4×256=1024 | 1 (impar) | rez×=256 → STOP |
4 pași în loc de 10 (metoda simplă). 2^10 = 1024 ✓
Problema 4: Fibonacci — recursiv vs iterativ
Metoda A: Recursiv (lent!)
int fib(int n) {
if (n <= 1) return n;
return fib(n-1) + fib(n-2); // se apelează de 2 ori!
}
// ~2^n apeluri — crește EXPONENȚIAL
Metoda B: Iterativ (rapid)
int fib(int n) {
if (n <= 1) return n;
int a = 0, b = 1;
for (int i = 2; i <= n; i++) {
int c = a + b;
a = b; b = c;
}
return b;
}
// n-1 pași — crește LINIAR
Comparație nr. apeluri/operații:
| n | Recursiv (apeluri) | Iterativ (pași) | Diferență |
|---|---|---|---|
| 10 | 177 | 9 | ~20x |
| 20 | 21.891 | 19 | ~1.150x |
| 30 | 2.692.537 | 29 | ~93.000x |
| 40 | 331.160.281 | 39 | ~8.500.000x |
Lecție: Recursivitatea e elegantă, dar poate fi extrem de lentă dacă recalculează aceleași valori. Fibonacci recursiv recalculează fib(5) de zeci de ori!
Trace: Fibonacci iterativ, n=7
| Pas (i) | a | b | c = a+b | fib(i) |
|---|---|---|---|---|
| — | 0 | 1 | — | fib(0)=0, fib(1)=1 |
| 2 | 1 | 1 | 1 | fib(2)=1 |
| 3 | 1 | 2 | 2 | fib(3)=2 |
| 4 | 2 | 3 | 3 | fib(4)=3 |
| 5 | 3 | 5 | 5 | fib(5)=5 |
| 6 | 5 | 8 | 8 | fib(6)=8 |
| 7 | 8 | 13 | 13 | fib(7)=13 |
6 pași (n-1). Recursivul ar fi făcut 41 de apeluri pentru n=7!
Greșeli frecvente în analiză
Eroare #1: Overflow la putere
Calculul 2^64 depășește long long! Pentru numere foarte mari, trebuie modular arithmetic: rez = (rez * baza) % MOD;
Eroare #2: Comparare doar pe cazuri mici
La n=10, ambele metode par rapide. Diferența se vede la n=1.000.000+. Testează mereu cu date mari pentru a vedea diferența reală.
Verificare: Alege algoritmul mai eficient
1. Numeri numerele pare de la 1 la 1.000.000. Ce metodă alegi?
2. Verifici dacă 999.983 e prim. Verifici până la:
3. Calculezi 3^1000. Câți pași face metoda rapidă?
4. Fibonacci(30) recursiv face ~2.7 milioane de apeluri. De ce?
5. CMMDC(1000000, 999997): Euclid face ~20 pași, for face ~999.997. De ce Euclid e mai rapid?
Extensie: cum alegi testele pentru o comparație corectă
O comparație între doi algoritmi este relevantă doar dacă îi testezi pe aceleași date și pe cazuri variate. Pentru analiza comparativă, nu este suficient să rulezi un singur exemplu mic.
Set minim de teste
- Caz mic: verifică ușor manual rezultatul.
- Caz mediu: observă diferența dintre metode.
- Caz mare: vezi clar cum crește timpul sau numărul de pași.
- Caz limită: n = 0, n = 1, valori egale sau element inexistent, după problemă.
| Ce compari | Măsură utilă | Exemplu |
|---|---|---|
| formulă vs buclă | număr de operații | suma 1+...+n |
| secvențial vs binar | număr de comparații | căutarea unei valori |
| metodă naivă vs eficientă | timp / pași | verificare prim sau CMMDC |
Întrebări frecvente (FAQ)
Nu neapărat! Pentru n mic (sub 100), diferența e neglijabilă. Alege codul mai ușor de citit dacă performanța nu contează. Dar la n mare, eficiența devine critică.
Adaugă o variabilă int pasi = 0; și incrementeaz-o (pasi++;) la fiecare operație semnificativă (comparație, calcul). La final, afișează pasi.
O(n) = nr. pași crește proporțional cu n (de 10x mai mare n → 10x mai mulți pași). O(log n) = nr. pași crește lent (de 10x mai mare n → doar +3 pași). Formula directă e O(1) = mereu 1 pas!
Recursivul formează un arbore exponențial. fib(5) apelează fib(4) și fib(3). fib(4) apelează fib(3) din nou! fib(3) se calculează de 2 ori, fib(2) de 3 ori. La fib(40), fib(2) se calculează de ~63 milioane de ori.
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 de executie pe calculatorul tau, deci poate iesi diferit pe alt calculator.
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; // prima pozitie pe care apare x
}
}
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: Analiză comparativă
Compară metode de rezolvare prin formule directe, bucle, căutare și măsurarea pașilor executați. Numărul de pași este mai important decât timpul exact, pentru că timpul depinde de calculator.
De ce long long? Suma 1+2+...+n crește repede. Pentru n = 100000, suma este 5000050000, mai mare decât limita unui int obișnuit.
Sarcina 1: Suma 1+2+...+n
Pași de rezolvare
- Metoda A:
for(i=1; i<=n; i++) suma += i;— O(n) pași - Metoda B:
suma = n * (n+1) / 2;— O(1), un singur pas - Cronometrează ambele cu
clock()pentru n=1.000.000 - Afișează: rezultat, timp. Folosește
long longpentru n mare!
Implementează 2 metode: (A) for cu sumă, (B) formula n*(n+1)/2. Compară nr. de operații pentru n=1.000.000.
De ce funcționează? Formula lui Gauss (n·(n+1)/2) dă suma primelor n numere naturale într-un singur pas O(1). For-ul parcurge fiecare număr → O(n) pași. La n=1.000.000, formula e de ~1.000.000× mai rapidă.
#include <iostream> // cin, cout
#include <ctime> // clock(), CLOCKS_PER_SEC
using namespace std;
int main(){
long long n = 1000000; // n mare pt diferență vizibilă
// ── Metoda A: for O(n) ──
clock_t s1 = clock(); // start cronometru
long long suma1 = 0;
for(long long i = 1; i <= n; i++)
suma1 += i; // adunăm fiecare i
clock_t e1 = clock(); // stop cronometru
// ── Metoda B: formula O(1) ──
clock_t s2 = clock();
long long suma2 = n * (n+1) / 2; // Gauss: un singur pas!
clock_t e2 = clock();
cout << "For: " << suma1 << " in "
<< double(e1-s1)/CLOCKS_PER_SEC << "s" << endl;
cout << "Formula: " << suma2 << " in "
<< double(e2-s2)/CLOCKS_PER_SEC << "s" << endl;
// Ambele dau 500000500000, dar for e mult mai lent
return 0;
}
Sarcina 2: Numere prime până la n
Pași de rezolvare
- For exterior:
for(num = 2; num <= n; num++) - For interior (optimizat):
for(d = 2; d*d <= num; d++) - Numără comparațiile totale cu un contor global
- Afișează: câte prime, câte comparații totale (așteptat ~114.000 pt n=10.000)
Generează toate numerele prime până la n=10.000. Folosește metoda √n. Numără câte verificări faci.
De ce funcționează? Dacă un număr num are un divizor d, atunci num/d e tot divizor și min(d, num/d) ≤ √num. Deci e suficient să testăm până la √num. La n=10.000, asta reduce comparațiile de la milioane la ~114.000.
#include <iostream>
using namespace std;
int main(){
int n = 10000; // limita superioară
int totalComp = 0; // contor global comparații
int nrPrime = 0; // câte prime am găsit
for(int num = 2; num <= n; num++){
bool prim = true;
// Verificăm doar până la √num (d*d ≤ num)
for(int d = 2; d*d <= num; d++){
totalComp++; // numărăm fiecare test
if(num % d == 0){ // găsit divizor → nu e prim
prim = false;
break; // nu mai testăm restul
}
}
if(prim) nrPrime++; // dacă n-am găsit divizor → prim
}
cout << "Prime gasite: " << nrPrime << endl; // 1229
cout << "Total comparatii: " << totalComp << endl; // ~114.000
return 0;
}