Divide et Impera (Metoda Divide et Impera, aplicatii)

Divide et Impera (în latină „desparte și stăpânește”) este o paradigmă fundamentală în proiectarea algoritmilor. Ea constă în trei etape esențiale: Divide (împarte problema în subprobleme mai mici, similare problemei originale), Impera (rezolvă recursiv fiecare subproblemă, până când acestea devin suficient de simple pentru a fi rezolvate direct – cazul de bază) și Combine (combină soluțiile subproblemelor pentru a obține soluția problemei inițiale). Metoda este eficientă atunci când subproblemele sunt independente și de același tip, iar complexitatea timpului este adesea O(n log n) sau O(log n), după cum indică Teorema Maestrului.

La liceu, cele mai frecvente aplicații sunt: Sortarea prin interclasare (Merge Sort), Sortarea rapidă (Quick Sort) și Căutarea binară (care folosește doar etapa de divide, fără combine, deoarece căutăm într-o singură parte). Alte exemple clasice sunt calculul ridicării la putere în timp logaritmic (fast exponentiation), determinarea valorii maxime/minime dintr-un vector și problema turnurilor din Hanoi.

Pentru Bacalaureat, este esențial să înțelegi cum se scrie recursiv un algoritm divide et impera: se identifică cazul de bază (de regulă dimensiune 0 sau 1), se împarte problema (de exemplu, la mijlocul vectorului) și se fac două apeluri recursive, iar apoi se combină rezultatele printr-o operație specifică (maxim, sumă, interclasare).

De asemenea, trebuie să poți determina complexitatea: pentru un algoritm care împarte problema în două subprobleme de dimensiuni aproximativ egale și combinarea se face în O(n), complexitatea totală este O(n log n). Pentru căutarea binară, combinarea este O(1), deci complexitatea este O(log n).

Atenție la implementare: în multe variante, subproblemele se definesc prin indici de început și sfârșit (stânga, dreapta), iar cazul de bază apare când stânga >= dreapta (sau când diferența este 1).

Exemple

• Exemplul 1: Căutare binară (Binary Search) – Se dă un vector sortat crescător și o valoare x. Algoritmul împarte vectorul la mijloc, compară x cu elementul din mijloc: dacă sunt egale, s-a găsit; dacă x < element, se caută în jumătatea stângă; altfel, în dreapta. Caz de bază: dacă stânga > dreapta, x nu există. Complexitate O(log n).
• Exemplul 2: Sortare prin interclasare (Merge Sort) – Se dă un vector. Se împarte în două jumătăți aproximativ egale. Se sortează recursiv fiecare jumătate. Apoi se interclasează cele două jumătăți sortate (se combină) pentru a obține vectorul sortat complet. Caz de bază: vector cu 0 sau 1 element. Complexitate O(n log n).
• Exemplul 3: Maximul dintr-un vector – Se împarte vectorul în două părți, se găsește maximul în fiecare parte recursiv, apoi se compară cele două maxime și se returnează cel mai mare. Caz de bază: vector cu un singur element, maximul este acel element. Complexitate O(n).

Concepte cheie: Divide et Impera: împărțirea problemei în subprobleme independente de același tip., Cazul de bază (condiția de oprire) pentru probleme de dimensiune suficient de mică., Combinarea soluțiilor subproblemelor pentru a forma soluția problemei inițiale., Aplicații principale: Merge Sort, Quick Sort, căutare binară, maxim/minim, ridicare la putere rapidă.