Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  


AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Interclasarea optima a sirurilor ordonate

c

+ Font mai mare | - Font mai mic





DOCUMENTE SIMILARE

Trimite pe Messenger
Stream-uri
Cateva aplicatii care “au in spate” C sau C++
Instructiunea switch
Memoria partajata
Tablouri unidimensionale - Vectori
Else-If
Citirea dintr-un fisier
Structuri cu autoreferire
Structuri de date dinamice
Memoria expandata

TERMENI importanti pentru acest document

Interclasarea optima a sirurilor ordonate

Se dau m vectori sortati crescator, v(i)=(v(i,1), , v(i, n(i)), i=1, , m si se cere algoritmul de interclasare a acestora cu numar minim de comparatii.




Rezolvare. Daca interclasarea a doi vectori v(1), v(2) o facem prin algoritmul prezentat anterior, atunci numarul de comparatii este cel mult n(1)+n(2). In functie de ordinea de interclasare a vectorilor se obtine un numar diferit de comparatii. Deci trebuie sa gasim o ordine care conduce la un numar minim de comparatii.

Exemplul 5.5

Vom nota cu v(i)v(j) vectorul obtinut prin interclasarea lui v(i) cu v(j). Daca avem v(1)=(2, 4, 6, 8), v(2)=(1, 2, 3) si v(3)=(1, 3, 5, 7, 9, 11) atunci:

  • Interclasarea (v(1) v(2)) v(3) se face cu cel mult (4+3)+(7+6) = 20 comparatii
  • Interclasarea (v(1) v(3)) v(2) se face cu cel mult (4+6)+(10+3) = 23 comparatii
  • Interclasarea (v(2) v(3)) v(1) se face cu cel mult (3+6)+(9+4) = 22 comparatii.

Din acest exemplu se observa ca este bine ca vectorii cu dimensiuni mici sa se interclaseze mai intai si apoi vectorii cu dimensiuni mari. Strategia Greedy va fi ca la fiecare pas sa selectam doi vectori de dimensiune minima.

La fiecare iteratie pastram in matricea v vectorii v(i) descrescator dupa n(i). Se selecteaza ultimii doi vectori din matricea v. Dupa realizarea interclasarii noul vector se insereaza in matricea v folosind, de exemplu, insertia directa.. Procedeul se repeta pana sunt interclasati toti vectorii.

(1)PROGRAM INTEROPT;

(2)BEGIN

READ M, (N(i),i:=1 TO M), ((V(I,J),I:=1 TO M),J:=1 TO N(I));

SORT(M, N, V);

FOR I:= M DOWNTO 2 DO

INTER(N(I-1), V(I-1), N(I), V(I), W);

J:=I-2;

WHILE (J>0) AND (N(J)<N(I-1)+N(I)) DO

FOR K:=1 TO N(J) DO

V(J+1,K):=V(J,K);

ENDFOR;

N(J+1):=N(J); J:=J-1;

ENDWHILE;

FOR K:=1 TO N(I-1)+N(I) DO

V(J+1,K):=W(K);

ENDFOR;

N(J+1):=N(I-1)+N(I);

(18) ENDFOR;

(19) WRITE V(1,J), 1 ≤ J ≤ N(1);

(20)END.

Procedura SORT face sortarea liniilor matricei v descrescator in functie de vectorul n si procedura INTER face interclasarea directa a doi vectori.

Pentru a analiza corectitudinea algoritmului definim printr-o formula recursiva arborele asociat unei strategii de interclasare.

  • Arborele asociat unui vector este format dintr-un nod ce are ca informatie numarul de elemente ale vectorului.
  • Arborele asociat interclasarii a doi vectori v(1) si v(2) este reprezentat in figura 5.7.



Fig. 5.7

  • Daca T1 este arborele asociat sirului de vectori v[i1], v[i2], …, v[ik] iar T2 este arborele asociat sirului de vectori v[ik+1], v[ik+2], …, v[in] atunci T este arborele asociat prin strategie sirului de vectori v[i1], v[i2], …, v[in] (vezi figura 5.8).

Fig. 5.8

Arborele asociat unui sir de vectori verifica urmatoarele afirmatii:

  • Are atatea frunze cati vectori sunt in sirul de vectori
  • Informatia atasata unui nod este suma dimensiunilor vectorilor din subarborele dat de nod
  • Daca un vector apare pe nivelul k atunci termenii sirului apar in exact k interclasari
  • Numarul total de comparatii dat de strategie este

, unde d[i] este nivelul in T al vectorului v[i].

Teorema 5.4

Algoritmul InterOpt determina interclasarea vectorilor v[i], i=1,n cu numar minim de comparatii realizate in interclasarile directe.

Demonstratie

Se observa ca arborele asociat unei strategii de interclasare este arborele Huffman asociat numerelor nr[1], nr[2], , nr[n]. Algoritmul anterior repeta modul de constructie al arborelui Huffman deci suma este minima si implicit L(T) este minim. Rezulta o strategie de interclasare optima.

Teorema 5.5

Daca L este numarul de comparatii rezultat din interclasarile directe atunci algoritmul InterOpt are complexitate O(L+n2).

Demonstratie

Complexitatea algoritmului este data de numarul de comparatii facut de interclasarile directe si de numarul de comparatii dat de pastrarea structurii v. In primul caz numarul este n. Pentru cel de-al doilea caz se observa ca inserarea directa foloseste cel mult i-1 comparatii pentru punerea sirului y in structura v. Gasim in total un numar de comparatii.

Daca se utilizeaza o inserare binara in structura v atunci complexitatea algoritmului devine O(L+nlogn).






Politica de confidentialitate



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 2398
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2021 . All rights reserved

Distribuie URL

Adauga cod HTML in site