Clasa a IX-a lecția 23 - 02 mai 2020: Difference between revisions

From Algopedia
Jump to navigationJump to search
(Undo revision 17764 by Teodor (talk))
Tag: Undo
 
(No difference)

Latest revision as of 07:15, 9 May 2020

Clasament teme lecțiile 1 - 22

Pe categorii

Divizori / Primalitate / Ciur
Sortari
Matrici
Cautare binara
Stivă
Recursivitate
Parcurgeri matrice
Generale

Concursuri

Probleme OȘI
Probleme OJI

Lecție

Divide et impera

Deși am folosit această tehnică în câteva aplicații recursive, acum vom intra mai în detaliu.

Tehnica de programare divide et impera constă în împărțirea problemei în subprobleme mai mici, nesuprapuse, care sunt mai ușor de rezolvat. Rezultatul final se obține combinând rezultatele problemelor mai mici deja rezolvate.

Divide et impera simplu

Exemple de probleme în care tehnica divide et impera împarte problema originală într-o singură problemă, mai simplă:

Algoritmul lui Euclid

Algoritmul lui Euclid poate fi privit ca un exemplu al tehnicii divide et impera. Acesta împarte problema de la aflarea cmmdc(a, b) la aflarea cmmdc(a % b, b).

Căutare binară

Căutarea binară împarte vectorul / mulțimea originală în două, algoritmul urmând să se aplice pe o singură ramură dintre acestea.

ZParcurgere

O problemă pe care am discutat-o anterior, rezolvată tot prin divide et impera, evaluând cadranul în care se află numărul nostru și apelând recursiv funcția pe acel cadran.


Observație Pentru aceste probleme, tehnica divide et impera se poate implementa iterativ, deoarece împărțim problema într-o singură altă problemă.

Divide et impera

Exemple de probleme în care tehnica divide et impera împarte problema originală în mai multe probleme:

Mergesort

Sortarea prin interclasare este o sortare în complexitate de timp O(N logN), folosind O(N) memorie suplimentară. Este prima sortare de această complexitate pe care o învățăm.

Cum funcționează? Ne vom folosi de proprietățile recursivității. Vom crea o funcție mergesort, care primește ca parametru un vector. La început, vom apela funcția pentru întreg vectorul inițial. Funcția va împărți vectorul în două părți egale, și se va apela pe ea însăși pentru ambele părți. Acest procedeu recursiv se va repeta până când funcția ajunge la un singur element. Ne putem întoarce atunci, pentru ca acel element reprezintă un vector sortat. La întoarcere din recursivitate, vom considera că funcția ne-a întors doi vectori sortați, iar noi îi vom interclasa pentru a întoarce la rândul nostru un vector sortat.

void mergesort(int v[], int left, int right) {
  if (left == right)                // Un singur element, deci "vectorul" format din acest singur element este sortat
    return;                         // Ne intoarcem
 
  int mid = (left + right) / 2;     // Mijlocul vectorului
  mergesort(v, left, mid);          // Sortam stanga
  mergesort(v, mid + 1, right);     // Sortam dreapta
 
  merge(v, left, mid, right);       // Functie care interclaseaza v[left...mid] cu v[mid + 1...right]
}
...
mergesort(v, 0, n - 1);

Complexitate timp

Să calculăm numărul de operații, T(N), pentru a sorta un vector de N elemente:

T(N) = 2 · T(N/2) + N
T(N) = 2 · (2 · T(N/4) + N/2) + N
T(N) = 4 · T(N/4) + 2 · N
T(N) = 4 · (2 · T(N/8) + N/4) + 2 · N
T(N) = 8 · T(N/8) + 3 · N
...
T(N) = N · T(N/N) + log N · N
T(N) = N · T(1) + log N · N

Deci, complexitatea de timp a algoritmului este O(N logN).

Complexitate spațiu

Funcția merge, responsabilă pentru interclasarea celor două jumătăți de vector are nevoie de un vector suplimentar. Deci, algoritmul folosește O(N) suplimentar.

Aplicație mergesort - inversiunile unei permutări

Sursă IQAcademy

O problemă care apare uneori la concursuri este următoarea: se dă o permutare a numerelor de la 1 la N. Să se numere cîte inversiuni are ea. O inversiune este o pereche de indici (i, j) astfel încît i < j și P[i] > P[j].

În linii mari, algoritmul este următorul:

  • Sortăm prima jumate a vectorului folosind un mergesort special, care ne returnează numărul de inversiuni din vectorul de sortat.
  • Sortăm a doua jumate a vectorului.
  • În acest moment știm inversiunile din cele două jumătăți - le adunăm.
  • Interclasăm cele două jumătăți. În timpul interclasării cînd selectăm un număr din prima jumătate știm că numerele deja selectate din jumătatea a doua sînt mai mici, deci putem aduna numărul lor la numărul total de inversiuni.

Quicksort

Un alt algoritm de sortare important este sortarea rapidă. Cum funcționează?

  • 1. Alegem o poziție la întâmplare din vectorul de sortat. Vom denumi valoarea de la acea poziție pivot.
  • 2. Rearanjăm vectorul astfel încât în prima parte să avem elemente mai mici sau egale cu pivotul iar în a doua parte elemente mai mari sau egale cu pivotul. Numim acest pas pivotare.
  • 3. Reapelăm quicksort pe acele două părți.

Trebuie să acordăm atenție la alegerea pivotului și la implementarea pasului de pivotare.

Alegerea pivotului

Similar cu mergesort, ar fi ideal ca la fiecare pas să împărțim vectorul în două părți cât mai egale ca dimensiune. Astfel, vom obține o complexitate de timp aproximativ egală cu O(N logN).

Se poate "nimeri" să alegem pivotul astfel încât la fiecare pas, să împărțim vectorul în doi vectori dintre care unul are dimensiunea 1. În acest caz, vom avea o complexitate de timp egală cu O(N2). Putem deduce de aici că pe cel mai rău caz, algoritmul poate face N2 pași.

Acest "cel mai rău caz" poate fi evitat în mare măsură printr-o alegere aleatoare a pivotului la fiecare pas. Vom atribui pivotului o valoare aleatoare între [left, right].

Pasul de pivotare

Am ales un pivot și vrem să rearanjăm vectorul astfel încât toate elementele mai mici sau egale cu acesta sunt la stânga lui, iar toate mai mari sau egale cu acesta sunt la dreapta.

  • Pornim cu doi indici, unul la începutul vectorului și unul la final de vector, să le spunem b si e.
  • Avansăm indicele b până la primul element mai mare sau egal cu pivotul
  • Devansăm indicele e până la primul element mai mic sau egal cu pivotul
  • Interschimbăm elementele din vector de la pozițiile b și e
  • Repetăm până ce indicii se ating, b >= e


void qsort(int v[], int begin, int end) {
  int pivot = v[begin + rand() % (end - begin)]; // alegem pivotul aleator

  int b = begin, e = end;
  while (v[b] < pivot) // cauta primul element mai mare sau egal cu pivotul
    b++;

  while (v[e] > pivot) // cauta primul element mai mic sau egal cu pivotul
    e--;

  while(b < e) {      // daca indicii nu s-au atins
    swap(v[b], v[e]); // interschimba pozitiile
    
    do                // cauta primul element mai mare sau egal cu pivotul
      b++;
    while (v[b] < pivot);

    do                // cauta primul element mai mic sau egal cu pivotul
      e--;
    while (v[e] > pivot);
  }

  // acum [begin..e] sunt mai mici sau egale cu pivotul
  if (begin < e)
    qsort(begin, e);
  // si [e+1..end] sunt mai mari sau egale cu pivotul
  if (e + 1 < end)
    qsort(e + 1, end);
}
...
qsort(v, 0, n);

Complexitate timp

Am discutat deja de complexitatea de timp, și anume O(N logN).

Complexitate spațiu

Complexitatea spațiu este egală cu numărul de apeluri recursive ale funcției. În urma discuției de la alegerea pivotului, avem o complexitate de spațiu suplimentar egală cu O(log N).

Sortarea din STL

Chiar dacă sortarea din STL poate fi suficient de rapidă, mai ușor de scris și își face treaba, este important să știți acești algoritmi prezentați astăzi. În sortările gata scrise din diverse librării ale limbajului de programare pe care îl folosiți nu aveți control total asupra tehnicii sau asupra memoriei folosite și puteți avea surprize neplăcute. Deci, recomand să folosiți aceste sortări ori de câte ori aveți posibilitatea, pentru a vă acomoda cu implementarea corectă a lor.

Temă

Rezolvați problema algsort, implementând ambii algoritmi de sortare învățați în lecția de astăzi.

latin - varena
tabela - varena
granita - infoarena
sport - infoarena