Pe scurt
Metoda Divide et Impera descompune o problemă complexă în subprobleme mai mici și independente, le rezolvă recursiv, apoi combină soluțiile pentru a obține rezultatul final. Algoritmii clasici care ilustrează această paradigmă sunt Merge Sort, Quick Sort și căutarea binară, având complexități de O(n log n), respectiv O(log n). Pentru bacalaureat, este esențială înțelegerea implementării recursive, a analizei complexității și a modului de combinare a soluțiilor.
Etapele algoritmice ale metodei Divide et Impera
- Divide – împărțirea problemei în două sau mai multe subprobleme de aceeași natură, dar de dimensiuni mai mici (de obicei, jumătate din dimensiunea originală)
- Impera – rezolvarea recursivă a fiecărei subprobleme, cu cazul de bază (subproblema trivială, de exemplu un singur element) care se rezolvă direct
- Combină – integrarea soluțiilor subproblemelor pentru a forma soluția problemei mari
Algoritmi clasici bazați pe Divide et Impera
Merge Sort (sortare prin interclasare)
- Împarte vectorul în două jumătăți egale
- Sortează recursiv fiecare jumătate
- Interclasează cele două secvențe ordonate într-un vector sortat
- Complexitate: O(n log n)
Exemplu: Vectorul inițial [38,27,43,3,9,82,10]
- Se împarte în [38,27,43,3] și [9,82,10]
- Se sortează recursiv fiecare: primul se divide în [38,27] și [43,3], apoi [38] și [27] → interclasare [27,38]; [43] și [3] → [3,43]; interclasare [3,27,38,43]
- Al doilea: [9,82,10] → [9,82] și [10]; [9] și [82] → [9,82]; interclasare [9,10,82]
- Final: interclasarea celor două jumătăți [3,27,38,43] și [9,10,82] → [3,9,10,27,38,43,82]
Quick Sort (sortare rapidă)
- Alege un pivot (elementul cheie pentru partiționare)
- Rearanjează elementele astfel încât toate cele mai mici decât pivotul să fie în stânga, iar cele mai mari în dreapta
- Sortează recursiv subvectorii stâng și drept
- Complexitate: O(n log n) în cazul mediu, O(n²) în cazul cel mai nefavorabil (de exemplu vector deja sortat)
Exemplu: Vectorul [10,80,30,90,40,50,70]
- Se alege pivot=70 (ultimul element)
- Se rearanjează: [10,30,40,50,70,80,90] (pivotul pe poziția 4)
- Se sortează recursiv stânga [10,30,40,50] (alegând pivot=50, rearanjare [10,30,40,50]) și dreapta [80,90] (pivot=90, rearanjare [80,90])
- Rezultat final: [10,30,40,50,70,80,90]
Căutarea binară (Binary Search)
- Se caută un element într-un vector sortat
- Împarte repetat intervalul de căutare în jumătăți și elimină jumătatea care nu poate conține elementul căutat
- Condiția de sortare: vectorul trebuie să fie sortat pentru căutare binară
- Complexitate: O(log n)
Exemplu: Vector sortat crescător v=[2,5,8,12,16,23,38,56,72,91] și valoarea x=23
- Se inițializează stânga=0, dreapta=9
- Se calculează mijlocul=(0+9)/2=4, v[4]=16 < 23, deci se caută în dreapta: stânga=5
- Noul mijloc=(5+9)/2=7, v[7]=56 > 23, deci dreapta=6
- Următorul mijloc=(5+6)/2=5, v[5]=23 == 23, s-a găsit pe poziția 5
Concepte cheie
- Divide: împărțirea problemei în subprobleme mai mici și independente
- Impera: rezolvarea recursivă a subproblemelor până la cazul de bază
- Combină: integrarea soluțiilor subproblemelor pentru a forma soluția finală
- Recursivitate: apelarea funcției în interiorul ei însăși
- Complexitate: analiza O(n log n) pentru sortări și O(log n) pentru căutarea binară
- Interclasare: operația de combinare în Merge Sort
Aplicații pentru bacalaureat
- Scrierea codului în pseudo-cod sau C++/Pascal pentru Merge Sort, Quick Sort sau căutare binară
- Aplicarea tehnicii pe probleme de genul „determinării celui de-al k-lea cel mai mic element” (prin Quick Select)
- Calculul numărului de inversiuni dintr-un vector (prin Merge Sort modificat)
Verifică-te!
- Care sunt cele trei etape principale ale metodei Divide et Impera și ce se întâmplă în fiecare dintre ele?
- Ce complexitate temporală au Merge Sort, Quick Sort (cazul mediu) și căutarea binară?
- Ce condiție trebuie îndeplinită de un vector pentru a putea aplica căutarea binară?