Embedded Files
Cuprins:
Cuprins:
Mergesort
Teorema Master
Metoda Master
1. MergeSort
1. MergeSort
Pentru a sorta cu mergesort folosim paradigma divide-et-impera:
Este prea complicat sa sortam un vector oarecare, dar stiu sa interclasez doi vectori deja-sortati crescator luand mereu minimul dintre cele doua siruri si punandu-l in rezultat.
Pentru a putea interclasa, trebuie sa produc probleme mai simple din problema mea complicata initiala: varianta imediata este prin impartire binara:
Impart problema in doua pana cand bucatile devin triviale: adica 1 element: adica vector sortat!
Interclasez bucatile astfel obtinute, pana cand recompun solutia problemei initiale.
#include <iostream>using namespace std;
void interclasare(int* v, int st, int dr){ int mid = (st+dr)/2; int index1=st; int index2=mid+1; int* r=new int[dr-st+1]; int r_index=0;//******INTERCLASARE******* while (index1<=mid&&index2<=dr){ if (v[index1]<=v[index2]) r[r_index++]=v[index1++]; else r[r_index++]=v[index2++]; } while (index1<=mid) r[r_index++]=v[index1++]; while (index2<=dr) r[r_index++]=v[index2++];//********************** for (index1=st;index1<=dr;index1++) v[index1]=r[index1-st]; delete[] r;}void mergesort(int* v, int st, int dr){ if (st<dr){ int mid = (st+dr)/2; mergesort(v,st,mid); mergesort(v,mid+1,dr); interclasare(v,st,dr); }}
int main(){ int v[]={53, 35, 72, 81, 22, 90, 14, 43, 61}; int n=sizeof(v)/sizeof(int); mergesort(v,0,n-1); for (int i=0;i<n;i++) cout<<v[i]<<" ";
return 0;}
void interclasare(int* v, int st, int dr){ int mid = (st+dr)/2; int index1=st; int index2=mid+1; int* r=new int[dr-st+1]; int r_index=0;//******INTERCLASARE******* while (index1<=mid&&index2<=dr){ if (v[index1]<=v[index2]) r[r_index++]=v[index1++]; else r[r_index++]=v[index2++]; } while (index1<=mid) r[r_index++]=v[index1++]; while (index2<=dr) r[r_index++]=v[index2++];//********************** for (index1=st;index1<=dr;index1++) v[index1]=r[index1-st]; delete[] r;}void mergesort(int* v, int st, int dr){ if (st<dr){ int mid = (st+dr)/2; mergesort(v,st,mid); mergesort(v,mid+1,dr); interclasare(v,st,dr); }}
int main(){ int v[]={53, 35, 72, 81, 22, 90, 14, 43, 61}; int n=sizeof(v)/sizeof(int); mergesort(v,0,n-1); for (int i=0;i<n;i++) cout<<v[i]<<" ";
return 0;}
Complexitate Interclasare
Complexitate Interclasare
Interclasarea a doi vectori de lungime n:
n citiri vector1
+ n citiri vector2
+ n comparatii v1[i]<v2[j]
+ 2n scrieri in vectorul rezultat
+ (2n incrementari de indecsi)
+ (2n comparatii de indecsi cu n)
= O( n )
Complexitate MergeSort
Complexitate MergeSort
Fie T(n) numarul de operatii al lui MergeSort.
La fiecare apel recursiv pe dimensiunea n:
cream doua subprobleme de dimensiune n/2
apoi solutia subproblemelor n/2 produce solutia problemei de dimensiune n prin interclasare in O(n)
Prin urmare:
T(n) = 2 T(n/2) + O(n)
T(n) = O(???)
Raspunsul este: T(n) = O( n log n )
Dorim un mecanism prin care sa aflam mai repede complexitatea functiilor recursive!
2. Teorema Master
2. Teorema Master
Enunt (a nu se utiliza sub aceasta forma):
Teorema master ne ofera o metoda unitara pentru determinarea timpului de rulare pentru toate functiile recursive de forma:
T(n) = aT(n/b) + f(n)
unde:
T(n) -> este o problema rezolvata recursiv prin impartire in subprobleme si combinarea solutiilor
T(n/b) -> este o subproblema
a -> este numarul de subprobleme
b -> controleaza dimensiunea subproblemei
f(n) -> reprezinta tot timpul necesar impartirii in subprobleme sau recombinarii solutiilor subproblemelor.
3. Metoda Master
3. Metoda Master
Google Sites
Report abuse