Informatică Algoritmi
Divide et impera principiu si exemple
Divide et impera este o tehnică de proiectare a algoritmilor care descompune o problemă complexă în subprobleme mai mici, similare. Se rezolvă fiecare subproblemă recursiv, apoi se combină soluțiile pentru a obține rezultatul final. Această abordare eficientizează procesarea datelor mari.
Pașii algoritmului
- 1 Divide Împarte problema inițială în subprobleme independente de aceeași natură, dar de dimensiuni reduse.
- 2 Impera Rezolvă recursiv fiecare subproblemă; dacă subproblema este suficient de mică, o tratează direct (caz de bază).
- 3 Combină Unește soluțiile subproblemelor pentru a forma soluția problemei originale.
Exemple clasice
- Sortare rapidă (Quicksort) Alege un pivot, împarte vectorul în elemente mai mici și mai mari decât pivotul, sortează recursiv fiecare parte, apoi le combină.
- Căutare binară Împarte un vector sortat la mijloc, compară elementul țintă cu mijlocul, și continuă recursiv în jumătatea relevantă.
- Înmulțirea matricelor Strassen Împarte matricele în submatrice, calculează produsele folosind formule recursive pentru a reduce complexitatea.
Începe cu implementarea căutării binare pe un vector de numere pentru a exersa divide et impera pe un caz simplu.