Ce sunt algoritmii Divide and Conquer? (Și nu, nu este „Divide and Concur”)

Divide and Conquer este o paradigmă algoritmică (uneori numită în mod eronat „Divide and Concur” – un nume amuzant și apt), asemănător programării Greedy și Dynamic. Un algoritm tipic Divide and Conquer rezolvă o problemă utilizând următorii trei pași.

  1. Divide: Împărțiți problema dată în subprobleme de același tip. Acest pas implică descompunerea problemei în subprobleme mai mici. Subproblemele ar trebui să reprezinte o parte a problemei inițiale. Acest pas adoptă, în general, o abordare recursivă pentru a împărți problema până când nici o sub-problemă nu este divizibilă în continuare. În acest stadiu, subproblemele devin de natură atomică, dar reprezintă încă o parte a problemei reale.
  2. A cuceri: Rezolvați recursiv aceste subprobleme. Acest pas primește o mulțime de sub-probleme mai mici de rezolvat. În general, la acest nivel, problemele sunt considerate „rezolvate” de la sine.
  3. Combina: Combinați în mod adecvat răspunsurile. Când sub-problemele mai mici sunt rezolvate, această etapă le combină recursiv până când formulează o soluție a problemei inițiale. Această abordare algoritmică funcționează recursiv și pașii de cucerire și îmbinare funcționează atât de aproape încât apar ca unul.

Această metodă ne permite de obicei să reducem complexitatea timpului într-o mare măsură.

De exemplu, Bubble Sort folosește o complexitate de O(n^2), în timp ce quicksort (o aplicație de divizare și cucerire) reduce complexitatea timpului la O(nlog(n)). Căutarea liniară are complexitate de timp O(n), în timp ce Binary Search (o aplicație de divizare și cucerire) reduce complexitatea timpului la O(log(n)).

Următoarele sunt câteva algoritmi standard care sunt din varietatea algoritmilor Divide and Conquer.

Căutare binară este un algoritm de căutare. În fiecare etapă, algoritmul compară elementul de intrare (x) cu valoarea elementului de mijloc din matrice. Dacă valorile se potrivesc, întoarceți indexul din mijloc. În caz contrar, dacă x este mai mic decât elementul de mijloc, atunci algoritmul se repetă în partea stângă a elementului de mijloc, altfel se repetă în partea dreaptă a elementului de mijloc.

Sortare rapida este un algoritm de sortare. Algoritmul alege un element pivot, rearanjează elementele matricei în așa fel încât toate elementele mai mici decât elementul pivot ales să se deplaseze în partea stângă a pivotului și toate elementele mai mari să se deplaseze în partea dreaptă. În cele din urmă, algoritmul sortează recursiv subarrayurile din stânga și din dreapta elementului pivot.

Merge Sort este, de asemenea, un algoritm de sortare. Algoritmul împarte matricea în două jumătăți, le sortează recursiv și, în cele din urmă, îmbină cele două jumătăți sortate. Complexitatea în timp a acestui algoritm este O(nLogn), fie că este cel mai bun caz, caz mediu sau cel mai rău caz. Complexitatea timpului poate fi ușor înțeleasă din recurență echivalează cu: T(n) = 2T(n/2) + n.

Cea mai apropiată pereche de puncte Problema este de a găsi cea mai apropiată pereche de puncte într-un set de puncte în planul xy. Problema poate fi rezolvată în O(n^2) timp calculând distanțele fiecărei perechi de puncte și comparând distanțele pentru a găsi minimul. Algoritmul Divide and Conquer rezolvă problema în O(nLogn) timp.

Algoritmul lui Strassen este un algoritm eficient pentru a multiplica două matrice. O metodă simplă pentru a multiplica două matrice are nevoie de 3 bucle imbricate și este O(n^3). Algoritmul lui Strassen înmulțește două matrice în O(n^2.8974) timp.

Algoritmul Cooley – Tukey Fast Fourier Transform (FFT) este cel mai comun algoritm pentru FFT. Este un algoritm de divizare și cucerire care funcționează în O(nlogn) timp.

Algoritmul Karatsuba a fost primul algoritm de multiplicare asimptotic mai rapid decât algoritmul pătratic „de școală de clasă”. Reduce înmulțirea a două numere din n cifre la cel mult la n ^ 1.585 (care este aproximarea logului de 3 în baza 2) produse dintr-o singură cifră. Prin urmare, este mai rapid decât algoritmul clasic, care necesită n ^ 2 produse dintr-o singură cifră.

Divide and Conquer (D & C) vs Dynamic Programming (DP)

Ambele paradigme (D & C și DP) împart problema dată în subprobleme și rezolvă subprobleme. Cum să alegeți una dintre ele pentru o anumită problemă? Divide and Conquer ar trebui să fie utilizate atunci când aceleași subprobleme nu sunt evaluate de multe ori. În caz contrar, ar trebui să se utilizeze Programare dinamică sau Memorizare.

De exemplu, Binary Search este un algoritm Divide and Conquer, nu mai evaluăm niciodată aceleași subprobleme. Pe de altă parte, pentru calcularea celui de-al nouălea număr Fibonacci, ar trebui preferată programarea dinamică.