CURSUL nr.05


predat in ziua de 03 noiembrie 2008


1. Volumul de comparari


In multe cazuri, eficienta utilizarii unei structuri de date se obtine prin compararea numarului de testari necesare in localizarea elementului din structura care are un identificator egal cu o cheie data.
Se considera vectorul X[N], avand N componente, toare initializate cu valorile crescatoare V1, V2, V3, V4, ..., VN, cu V1 < V2 < V3 < ... < VN.
daca se considera M chei K1, K2, K3, K4, ..., KM, cu M << N, chei ordonate, de asemenea crescator, K1 < K2 < K3 < ... < KM, trebuie facuta o analiza asupra volumului de comparatii(teste) care sunt necesare pentru a gasi in vector elementele care contin valori identice cu cheile.
Cazul cel mai putin favorabil consta in a da M chei care nu se regasesc printre valorile vectorului.
Numarul maxim de comparari NCmax , depinde de:
- numarul M al cheilor
- numarul N al componentelor din vector care se traverseaza.
NCmax = M * N
Daca cele M chei sunt identice si corespund primului element din vector, ceea ce presupune de fiecare data cate o singura comparatie, numarul minim de comparari NC min este:
NC min = M
Rezulta ca orice problema P care utilizeaza un vector cu N componente si apare necesitatea de a cauta M elemente folosind comparatii, volumul de comparari V respecta relatia:
NC min < V < NCmax.
Intrucat este putin probabil sa apara cele doua ipoteze, se vor lua in considerare urmatoarele situatii:
- situatia cea mai favorabila, incare cele M chei corespund chiar primelor elemente din sir, fiind deci necesare 1, 2, 3, ..., M comparari; numarul de comparari NCC este dat de relatia:
NCC = 1 + 2 + 3 + 4 +...+ M = M * (M+1)/2 - situatia cea mai nefavorabila in care toate cele M chei corespund ultimelor elemente din vector, fiind necesare N-M, N-M+1, N-M+2, ..., N-2, N-1, N comparari, adica un volum de comparari, NNC dat de relatia:
NNC = N * (N + 1)/2 - (N-M)*(N-M+1)/2
Deci:
M * (M+1)/2 < V < [(M-1)*(2N-1)-1]/2
In cazul listelor simple, a listelor duble, aspectele legate de volumul de comparari se obtin cu ipoteze construite in mod asemanator.
Pentru o structura arborescenta binara, numarul de comparatii impune luarea in considerare a urmatoarelor ipoteze:
- arborele binar are N niveluri; radacina este pe nivelul 1, cei doi descendenti directi ai radacinii sunt pe nivelul 2, pe nivelul 3 se afla 4 descendenti, iar pe nivelul K se afla 2K-1 descendenti;
- numarul total de noduri NTN in arborele binar este obtinut din insumarea numarului de noduri de pe fiecare nivel, adica pe nivelul 1, sunt 2K-1-1 noduri, pe nivelul 2 sunt 22-1, pe nivelul 3 sunt 2K-3-1 noduri, iar pe ultimul nivel, nivelul N sunt 2N-1, se obtine suma termenilor unei progresii geometrice:
NTN = 21-1 + 22-1 + 23-1 + ... 2N-1 = 2N - 1 noduri
- trebuie gasite nodurile care au ca informatie utila, campuri egale cu M chei
- situatia cea mai putin favorabila corespunde dispunerii tuturor nodurilor cu cheile cautate in nodurile frunza ale structurii arborescente, trebuind sa se efecteueze comparari de la radacina spre frunza pe toata inaltimea arborelui, adica N comparari pentru fiecare cheie, numarul de comparari defavorabil NDA fiind:
NDA = N * M comparari
- situatia cea mai favorabilaeste data de cazul in care cele M chei sunt identice si corespund informatiei aflate in nodul radacina, trebuind de fiecare data o singura comparatie.
Volumul de comparari V trebuie sa respecte cerinta:
N < V < N*M

2. Coada


in lucru acum....



afisat azi 7 octombrie 2008

REVENIRE