Ce vei învăța astăzi?
După această lecție vei învăța să compari metodele de sortare după eficiență, folosind numărul de comparații și notația O.
Numărul de comparații
La selecția minimului și la metoda bulelor, numărul de comparații (operațiile prin care comparăm două elemente între ele) este aproximativ n(n-1)/2. Acesta crește foarte repede odată cu n.
| n (elemente) | Comparații ≈ n(n-1)/2 |
|---|---|
| 10 | 45 |
| 100 | 4950 |
| 1000 | 499500 |
Observă: dacă dublăm n, numărul de comparații se aproximează de 4 ori mai mare. De aceea vorbim de O(n²).
Sortarea cu lista de frecvențe
Pentru valori dintr-un interval mic, lista de frecvențe este mult mai rapidă: face aproximativ n + max operații (numără aparițiile și apoi le afișează).
Cursa metodelor
Imaginează-ți 1000 de note de sortat: metoda bulelor face aproximativ 500.000 de comparații, în timp ce lista de frecvențe face doar aproximativ 1010 operații. Diferența este uriașă!
Notația O, introdusă simplu
Notația O (modul scurt de a nota cât de repede crește numărul de operații) ne spune cât de repede crește timpul de execuție când crește numărul de elemente:
O(n²) - timpul crește cu pătratul lui n (bulele, selecția minimului).
O(n) - timpul crește liniar, adică proporțional cu numărul de elemente (lista de frecvențe).
| Notație | Ce înseamnă | Exemplu |
|---|---|---|
| O(n²) | Timpul crește cu pătratul lui n | Metoda bulelor, selecția minimului |
| O(n) | Timpul crește liniar | Lista de frecvențe, căutarea unui minim |
Gândește: dacă dublezi numărul de note, la O(n) timpul se dublează, dar la O(n²) se înmulțește cu 4.
Când alegem fiecare metodă
Nu există o metodă perfectă pentru orice situație. Alegem după datele problemei. Iată două programe care numără comparațiile la selecție și la bule pe aceeași listă:
Comparații la selecția minimului
v = [6, 2, 8, 4, 1, 9, 3]
n = len(v)
nr = 0
for i in range(n - 1):
p = i
for j in range(i + 1, n):
nr = nr + 1
if v[j] < v[p]:
p = j
v[i], v[p] = v[p], v[i]
print("Comparatii la selectie:", nr)
print(v)
Comparații la metoda bulelor
v = [6, 2, 8, 4, 1, 9, 3]
n = len(v)
nr = 0
for i in range(n - 1):
for j in range(n - 1 - i):
nr = nr + 1
if v[j] > v[j + 1]:
v[j], v[j + 1] = v[j + 1], v[j]
print("Comparatii la bule:", nr)
print(v)
Observă: ambele numără un nr de comparații aproape egal cu n(n-1)/2, pentru că ambele compară perechi de elemente.
Exercițiu de completare
Completează propozițiile despre eficiența sortărilor:
Numărul de ______ la metoda bulelor este aproximativ n(n-1)/2. Notăm această complexitate cu O(______). Pentru valori dintr-un interval mic folosim lista de ______. Notația care descrie numărul de operații se numește notația ______.
Bancă de cuvinte:
Test de înțelegere
Test rapid - eficiența sortărilor:
1. Pentru n = 100, numărul de comparații la metoda bulelor este aproximativ:
2. Care metodă este cea mai rapidă pentru note de la 1 la 10?
3. Complexitatea metodelor bulelor și selecției minimului este:
Test suplimentar - verifică ce ai reținut
Test rapid suplimentar - eficiența sortărilor:
1. Selecția minimului și metoda bulelor au complexitatea:
2. Lista de frecvențe are complexitatea:
3. Când n este foarte mare și valorile sunt într-un interval mic, alegem:
Aprofundare
Eficiența nu este doar o teorie: ea decide dacă un program rulează în timp util. La un concurs sau examen, un program care face prea multe operații poate depăși timpul permis, chiar dacă răspunsul ar fi corect.
- Creșterea concretă a efortului: pentru n = 10, O(n²) înseamnă aproximativ 45 de comparații; pentru n = 100, 4950; pentru n = 1000, 499500; pentru n = 100000, aproape 5 miliarde - un program care face 5 miliarde de operații rulează mult prea lent.
- O(n²) vs O(n): dacă dublăm n, timpul unei metode O(n) se dublează, dar timpul unei metode O(n²) se înmulțește cu 4; diferența devine uriașă pe măsură ce n crește.
- Memoria suplimentară: lista de frecvențe folosește memorie proporțională cu intervalul de valori (max + 1 elemente), în timp ce selecția minimului și bulele sortează „în loc", fără memorie suplimentară.
- Alegerea după restricții: dacă problema spune că valorile sunt între 1 și 1000 și n este mare, lista de frecvențe este alegerea sigură; dacă valorile sunt oricât de mari, folosim O(n²) doar pentru n rezonabil (până la câteva mii).
- Numărarea operațiilor: putem măsura efortul real adăugând un contor
nr = nr + 1în bucla interioară, exact ca în exemplele lecției, și comparând rezultatele pe aceeași listă.
PbInfo - Numărul de interschimbări la metoda bulelor
Enunț:
Cerință: Se citește numărul natural n și apoi n numere întregi. Să se afișeze de câte ori s-au interschimbat elemente în timpul sortării prin metoda bulelor.
Date de intrare:
Programul citește de la tastatură numărul n, apoi n numere întregi.
Date de ieșire:
Programul va afișa numărul de interschimbări efectuate.
Restricții și precizări:
n este un număr natural, cu 1 <= n <= 1000, iar elementele sunt numere întregi.
Exemplu:
Intrare:
5 6 2 8 4 1
Ieșire:
7
Cum gândim soluția:
- Citim n și vectorul v
- Sortăm prin metoda bulelor
- De fiecare dată când interschimbăm, creștem un contor nr
- Afișăm contorul la final
Scrie soluția în Python:
Soluție corectă:
n = int(input())
v = list(map(int, input().split()))
nr = 0
for i in range(n - 1):
for j in range(n - 1 - i):
if v[j] > v[j + 1]:
v[j], v[j + 1] = v[j + 1], v[j]
nr = nr + 1
print(nr)
Ce învățăm: folosim un contor pe care îl creștem doar în interiorul interschimbării, pentru a număra exact operațiile făcute.
PbInfo - Sortare eficientă cu lista de frecvențe
Enunț:
Cerință: Se citesc n scoruri, numere întregi între 0 și 100. Să se afișeze scorurile sortate crescător folosind lista de frecvențe.
Date de intrare:
Programul citește de la tastatură numărul n, apoi cele n scoruri.
Date de ieșire:
Programul va afișa scorurile sortate crescător, separate prin spații.
Restricții și precizări:
n este un număr natural, cu 1 <= n <= 1000, iar elementele sunt numere întregi.
Exemplu:
Intrare:
7 85 92 40 92 60 85 40
Ieșire:
40 40 60 85 85 92 92
Cum gândim soluția:
- Citim n și vectorul v
- Construim fr = [0] * 101 și incrementăm fr[x] pentru fiecare scor x
- Parcurgem i de la 0 la 100 și afișăm i de fr[i] ori
Scrie soluția în Python:
Soluție corectă:
n = int(input())
v = list(map(int, input().split()))
fr = [0] * 101
for x in v:
fr[x] = fr[x] + 1
for i in range(101):
for _ in range(fr[i]):
print(i, end=" ")
Ce învățăm: alegem lista de frecvențe pentru valori într-un interval mic (0-100), ceea ce face sortarea foarte rapidă.
Exercițiul Practic: Compararea metodelor de sortare
Sarcini de lucru
Compară eficiența metodelor în programe complete și aplică lista de frecvențe pe date reale.
Sarcina 1: Interschimbări la bule vs selecție
Cerință: Scrie un program care compară numărul de interschimbări făcute de metoda bulelor și de selecția minimului pe aceeași listă și afișează ambele contoare.
Soluție:
def sortare_bule(v):
v = v[:]
nr = 0
for i in range(len(v) - 1):
for j in range(len(v) - 1 - i):
if v[j] > v[j + 1]:
v[j], v[j + 1] = v[j + 1], v[j]
nr = nr + 1
return nr
def sortare_selectie(v):
v = v[:]
nr = 0
for i in range(len(v) - 1):
p = i
for j in range(i + 1, len(v)):
if v[j] < v[p]:
p = j
if p != i:
v[i], v[p] = v[p], v[i]
nr = nr + 1
return nr
v = [6, 2, 8, 4, 1, 9, 3]
print("Interschimbari la bule:", sortare_bule(v))
print("Interschimbari la selectie:", sortare_selectie(v))
Observă: metoda bulelor face mai multe interschimbări, iar selecția minimului face cel mult una pe pas.
Sarcina 2: Primele 10 scoruri descrescător
Cerință: Scrie un program care citește n scoruri (0-100), le sortează cu lista de frecvențe și afișează primele 10, în ordine descrescătoare.
Soluție:
n = int(input())
v = list(map(int, input().split()))
fr = [0] * 101
for x in v:
fr[x] = fr[x] + 1
afisate = 0
for i in range(100, -1, -1):
for _ in range(fr[i]):
print(i, end=" ")
afisate = afisate + 1
if afisate == 10:
break
if afisate == 10:
break
Verifică: parcurgem pozițiile de la 100 în jos și ne oprim după 10 valori afișate.