Algoritmul Divide and Conquer este o strategie de rezolvare a problemelor care implică împărțirea unei probleme complexe în părți mai mici, mai ușor de gestionat, rezolvarea fiecărei părți în mod individual și apoi combinarea soluțiilor pentru a rezolva problema inițială. Este o tehnică algoritmică utilizată pe scară largă în informatică și matematică.

Exemplu: În Merge Sort algoritmul, cel Diviza și cuceri strategia este folosită pentru a sorta o listă de elemente. Imaginea de mai jos ilustrează stările de împărțire și îmbinare pentru a sorta matricea folosind Merge Sort .

Cuprins

• Ce este Divide and Conquer?
• Etapele Divide and Conquer
• Aplicații ale lui Divide and Conquer
• Bazele Divide and Conquer
• Algoritmi standard pentru împărțirea și cucerirea
• Probleme bazate pe căutare binară
• Exersați probleme la Divide and Conquer

Ce este algoritmul Divide and Conquer?

Divide and Conquer este o tehnică de rezolvare a problemelor care implică împărțirea unei probleme mai mari în subprobleme, rezolvarea subproblemelor în mod independent și combinarea soluțiilor acelor subprobleme pentru a obține soluția problemei mai mari.

Etapele algoritmului Divide and Cuquer:

Algoritmul Divide and Conquer poate fi împărțit în trei etape: Divide , A cuceri și Combina .

1. Împărțiți:

• Împărțiți problema inițială în subprobleme mai mici.
• Fiecare subproblemă ar trebui să reprezinte o parte a problemei generale.
• Scopul este de a împărți problema până când nu mai este posibilă o altă împărțire.

2. Cuceri:

• Rezolvați fiecare dintre subproblemele mai mici individual.
• Dacă o subproblemă este suficient de mică (denumită adesea cazul de bază), o rezolvăm direct fără recursuri suplimentare.
• Scopul este de a găsi soluții pentru aceste subprobleme în mod independent.

3. Îmbinați:

• Combinați sub-problemele pentru a obține soluția finală a întregii probleme.
• Odată rezolvate subproblemele mai mici, combinăm recursiv soluțiile lor pentru a obține soluția problemei mai mari.
• Scopul este de a formula o soluție pentru problema inițială prin îmbinarea rezultatelor din subprobleme.

Aplicații ale algoritmului Divide and Conquer:

• Sortare îmbinare: Sortarea prin îmbinare este un exemplu clasic de algoritm de sortare împărțiți și cuceriți. Acesta descompune matricea în subgrupuri mai mici, le sortează individual și apoi le îmbină pentru a obține matricea sortată.
• Constatare mediană: Mediana unui set de numere poate fi găsită folosind o abordare împărțire și cuceri. Împărțind recursiv mulțimea în submulțimi mai mici, mediana poate fi determinată eficient.
• Constatare min și max: Algoritmul Divide and Conquer poate fi folosit pentru a găsi simultan atât elementele minime, cât și cele maxime dintr-o matrice. Prin împărțirea matricei în jumătăți și comparând perechile min-max din fiecare jumătate, totalul min și max poate fi identificat în complexitatea timpului logaritmic.
• Înmulțirea matricei: Algoritmul lui Strassen pentru înmulțirea matricelor este o tehnică de împărțire și cucerire care reduce numărul de înmulțiri necesare pentru matrici mari prin descompunerea matricelor în submatrici mai mici și combinând produsele lor.
• Problema cu cea mai apropiată pereche: Problema perechii celei mai apropiate implică găsirea celor mai apropiate două puncte dintr-un set de puncte dintr-un spațiu multidimensional. Un algoritm de împărțire și cucerire, cum ar fi algoritmul de împărțire și cuceri, cea mai apropiată pereche, poate rezolva eficient această problemă prin împărțirea recursiv a punctelor și îmbinarea soluțiilor din subprobleme.

Bazele algoritmului Divide and Conquer:

• Introducere în Divide and Conquer
• Programare dinamică vs Divide-and-Conquer
• Scădeți și cuceriți
• Teorema principală avansată pentru împărțirea și cucerirea recurențelor

Algoritmi standard activați Algoritmul Divide and Conquer :

• Căutare binară
• Merge Sort
• Sortare rapida
• Calculați pow(x, n)
• Algoritm Karatsuba pentru multiplicare rapidă
• Înmulțirea matricei a lui Strassen
• Carcasă convexă (algoritm simplu de împărțire și cucerire)
• Algoritmul Quickhull pentru Hull convex

Probleme bazate pe căutare binară:

• Găsiți un element de vârf într-o matrice dată
• Verificați elementul majoritar într-o matrice sortată
• K-lea element din două tablouri sortate
• Aflați numărul de zerouri
• Găsiți numărul de rotații în matrice Rotated Sorted
• Găsiți punctul în care o funcție crescătoare monotonă devine pozitivă prima dată
• Mediana a două matrice sortate
• Mediana a două matrice sortate de dimensiuni diferite
• Problema partiției pictorului folosind Căutare binară

Practicați problemele pe Algoritmul Divide and Conquer :

• Rădăcina pătrată a unui număr întreg
• Maximul și minimul unei matrice folosind numărul minim de comparații
• Găsiți frecvența fiecărui element într-o matrice cu interval limitat în mai puțin de timp O(n).
• Problemă cu gresie
• Numără inversiuni
• Problema orizontului
• Căutați într-o matrice 2D sortată pe rând și pe coloane
• Alocați un număr minim de pagini
• Exponentiație modulară (putere în aritmetică modulară)

Link-uri rapide:

• Aflați structura datelor și algoritmi | Tutorial DSA
• „Probleme de practică” la Divide and Conquer
• „Chestionare” despre Divide and Conquer