Informatică Programare
Algoritmi divide et impera C++
Algoritmii divide et impera în C++ descompun o problemă în subprobleme mai mici, similare, le rezolvă recursiv și combină rezultatele. Această tehnică este eficientă pentru sortare sau căutare.
Etape principale
- 1 Divide Împarte problema în subprobleme mai mici și independente. Exemplu: pentru un vector, îl împarte în două jumătăți.
- 2 Stăpânește (Impera) Rezolvă subproblemele recursiv. Dacă sunt suficient de mici, le rezolvă direct (caz de bază).
- 3 Combină Unește soluțiile subproblemelor pentru a obține soluția problemei inițiale.
Exemplu: Merge Sort
- Divide Vectorul este împărțit recursiv în subvectori până când fiecare are un singur element.
- Impera Subvectorii cu un element sunt deja sortați (caz de bază).
- Combină Subvectorii sortați sunt interclasați pentru a forma vectori mai mari sortați.
- Complexitate O(n log n), deoarece împărțirea este logaritmică și interclasarea liniară.
Alege divide et impera pentru probleme cu substructură optimă, ca sortarea sau căutarea binară.