Pe scurt
Divide et impera este o paradigmă fundamentală în proiectarea algoritmilor, bazată pe trei etape: împărțirea problemei în subprobleme mai mici, rezolvarea recursivă a acestora și combinarea soluțiilor. Aplicațiile clasice studiate la bacalaureat sunt căutarea binară (O(log n)), mergesort (O(n log n)) și quicksort (O(n log n) în cazul mediu).
Principiul divide et impera
Paradigma divide et impera („desparte și stăpânește") se bazează pe trei etape:
- Divide: problema este împărțită în subprobleme mai mici, similare cu cea originală
- Impera: subproblemele sunt rezolvate recursiv (sau direct dacă sunt suficient de mici – caz de bază)
- Combină: soluțiile subproblemelor sunt combinate pentru a obține soluția problemei inițiale
Această tehnică reduce complexitatea temporală în multe cazuri de la O(n²) la O(n log n).
Căutarea binară
Căutarea binară caută un element într-un vector sortat prin împărțirea repetată a intervalului de căutare în jumătăți.
- Complexitate: O(log n)
- Este un exemplu perfect de divide et impera (fără combinare, deoarece rezultatul este direct)
Pași
- Se compară elementul din mijloc cu valoarea căutată
- Dacă sunt egale, s-a găsit
- Altfel se continuă în jumătatea stângă sau dreaptă
Exemplu: Fie vectorul sortat [1, 3, 5, 7, 9, 11, 13] și valoarea căutată x=7.
- Se calculează mijlocul între stânga=0 și dreapta=6 → mid=3, elementul este 7, egal cu x, se returnează poziția 3
- Dacă x=6: mid=3 → 7>6, se continuă cu dreapta=2; mid=1 → 3<6, stânga=2; mid=2 → 5<6, stânga=3; interval gol → nu există
Mergesort (sortare prin interclasare)
Mergesort împarte vectorul în două jumătăți egale, sortează recursiv fiecare jumătate, apoi interclasează cele două jumătăți sortate.
- Complexitate: O(n log n) în toate cazurile
- Stabil
- Memorie auxiliară: O(n)
Exemplu: Vector [4, 2, 7, 1, 9, 3]
- Se împarte în [4,2,7] și [1,9,3]
- Se sortează recursiv: stânga → [2,4,7], dreapta → [1,3,9]
- Se interclasează: se compară primii elemente 2 vs 1 → 1, apoi 2 vs 3 → 2, apoi 4 vs 3 → 3, apoi 4 vs 9 → 4, apoi 7 vs 9 → 7, apoi 9 din dreapta → [1,2,3,4,7,9]
Quicksort (sortare rapidă)
Quicksort alege un pivot, rearanjează elementele astfel încât cele mai mici decât pivotul să fie în stânga, iar cele mai mari în dreapta (operația Partition), apoi sortează recursiv cei doi subvectori.
- Complexitate medie: O(n log n)
- Cel mai defavorabil: O(n²) (când pivotul este ales prost)
- Se poate optimiza alegând pivotul ca mediană dintre trei elemente
- Sortare in-place
Exemplu: Vector [3,6,1,8,4,2]
- Se alege pivotul 4 (ultimul element)
- Partition: parcurgem vectorul cu indicele i, j; la final pivotul se plasează între elementele mai mici și mai mari
- Rezultat parțial: [3,1,2,4,8,6]
- Se sortează rec. stânga [3,1,2] și dreapta [8,6]
- Pentru stânga, pivot 2: devine [1,2,3]
- Pentru dreapta, pivot 6: devine [6,8]
- Final: [1,2,3,4,6,8]
Relația de recurență
Pentru bacalaureat, elevii trebuie să cunoască relația de recurență: **T(n) = a*T(n/b) + O(n^k), unde:
- a = numărul de subprobleme
- b = factorul de reducere
- O(n^k) = costul combinării
Aplicații
- Pentru mergesort: a=2, b=2, k=1 ⇒ T(n)=O(n log n)
- Pentru căutare binară**: a=1, b=2, k=0 ⇒ O(log n)
Cerințe pentru bacalaureat
Elevii trebuie să
- Implementeze acești algoritmi în pseudocod sau limbaj C/C++/Python
- Analizeze complexitatea
- Recunoască situațiile de aplicare
- Cunoască relația de recurență și aplicarea teoremei master
Verifică-te!
- Care sunt cele trei etape ale paradigmei divide et impera și ce se întâmplă în fiecare dintre ele?
- De ce căutarea binară are complexitatea O(log n), în timp ce mergesort are O(n log n)?
- În ce condiții quicksort are complexitatea O(n²) și cum poate fi evitată această situație?