Verdeel en heers Algoritme is een probleemoplossende techniek die wordt gebruikt om problemen op te lossen door het hoofdprobleem in deelproblemen te verdelen, deze afzonderlijk op te lossen en ze vervolgens samen te voegen om een ​​oplossing voor het oorspronkelijke probleem te vinden. In dit artikel gaan we bespreken hoe het verdeel-en-heers-algoritme nuttig is en hoe we het kunnen gebruiken om problemen op te lossen.

Inhoudsopgave

• Verdeel en heers algoritmedefinitie
• Werking van het verdeel en heers-algoritme
• Kenmerken van het verdeel en heers-algoritme
• Voorbeelden van verdeel en heers-algoritme
• Complexiteitsanalyse van verdeel en heers-algoritme
• Toepassingen van het verdeel en heers-algoritme
• Voordelen van het verdeel en heers-algoritme
• Nadelen van het verdeel en heers-algoritme

Verdeel en heers Algoritmedefinitie:

Verdeel en heers algoritme Het gaat om het opsplitsen van een groter probleem in kleinere deelproblemen, deze onafhankelijk op te lossen en vervolgens hun oplossingen te combineren om het oorspronkelijke probleem op te lossen. Het basisidee is om het probleem recursief in kleinere deelproblemen te verdelen, totdat ze eenvoudig genoeg worden om direct opgelost te worden. Zodra de oplossingen voor de deelproblemen zijn verkregen, worden ze vervolgens gecombineerd om de algehele oplossing te produceren.

Werking van het verdeel en heers-algoritme:

Het verdeel-en-heers-algoritme kan in drie stappen worden onderverdeeld: Verdeling , Veroveren En Samenvoegen .

1. Verdeel:

• Verdeel het oorspronkelijke probleem in kleinere deelproblemen.
• Elk deelprobleem moet een deel van het totale probleem vertegenwoordigen.
• Het doel is om het probleem te verdelen totdat er geen verdere verdeling meer mogelijk is.

2. Verover:

• Los elk van de kleinere deelproblemen afzonderlijk op.
• Als een deelprobleem klein genoeg is (vaak het basisprobleem genoemd), lossen we het direct op, zonder verdere recursie.
• Het doel is om voor deze deelproblemen zelfstandig oplossingen te vinden.

3. Samenvoegen:

• Combineer de deelproblemen om de uiteindelijke oplossing van het hele probleem te krijgen.
• Zodra de kleinere deelproblemen zijn opgelost, combineren we hun oplossingen recursief om de oplossing van een groter probleem te krijgen.
• Het doel is om een ​​oplossing voor het oorspronkelijke probleem te formuleren door de resultaten van de deelproblemen samen te voegen.

Kenmerken van het verdeel en heers-algoritme:

Het verdeel-en-heers-algoritme houdt in dat je een probleem opsplitst in kleinere, beter beheersbare delen, elk deel afzonderlijk oplost en vervolgens de oplossingen combineert om het oorspronkelijke probleem op te lossen. De kenmerken van het Verdeel en Heers-algoritme zijn:

• Het probleem verdelen : De eerste stap is het probleem opdelen in kleinere, beter beheersbare deelproblemen. Deze verdeling kan recursief worden uitgevoerd totdat de deelproblemen eenvoudig genoeg worden om direct op te lossen.
• Onafhankelijkheid van deelproblemen : Elk deelprobleem moet onafhankelijk zijn van de andere, wat betekent dat het oplossen van het ene deelprobleem niet afhankelijk is van de oplossing van een ander deelprobleem. Dit maakt parallelle verwerking of gelijktijdige uitvoering van deelproblemen mogelijk, wat tot efficiëntiewinsten kan leiden.
• Elk subprobleem overwinnen : Eenmaal verdeeld, worden de deelproblemen afzonderlijk opgelost. Dit kan inhouden dat dezelfde verdeel-en-heers-aanpak recursief wordt toegepast totdat de deelproblemen eenvoudig genoeg worden om direct op te lossen, of het kan inhouden dat een ander algoritme of een andere techniek wordt toegepast.
• Oplossingen combineren : Na het oplossen van de deelproblemen worden hun oplossingen gecombineerd om de oplossing voor het oorspronkelijke probleem te verkrijgen. Deze combinatiestap moet relatief efficiënt en eenvoudig zijn, omdat de oplossingen voor de deelproblemen zo moeten worden ontworpen dat ze naadloos op elkaar aansluiten.

Voorbeelden van verdeel en heers-algoritme:

1. Het maximale element in de array vinden:

We kunnen het Divide and Conquer-algoritme gebruiken om het maximale element in de array te vinden door de array in twee subarrays van gelijke grootte te verdelen, en het maximum van die twee individuele helften te vinden door ze opnieuw in twee kleinere helften te verdelen. Dit wordt gedaan totdat we subarrays van grootte 1 bereiken. Nadat we de elementen hebben bereikt, retourneren we het maximale element en combineren we de subarrays door het maximum in elke subarray terug te geven.

// function to find the maximum no. // in a given array. int findMax(int a[], int lo, int hi) {  // If lo becomes greater than hi, then return minimum  // integer possible  if (lo>hallo) retour INT_MIN;  // Als de subarray slechts één element bevat, retourneert u het // element if (lo == hi) retourneert a[lo];  int midden = (lo + hi) / 2;  // Haal het maximale element uit de linkerhelft int leftMax = findMax(a, lo, mid);  // Haal het maximale element uit de rechterhelft int rightMax = findMax(a, mid + 1, hi);  // Retourneer het maximale element van links en rechts // half return max(leftMax, rightMax); }>

// Function to find the maximum number // in a given array. static int findMax(int[] a, int lo, int hi) {  // If lo becomes greater than hi, then return  // minimum integer possible  if (lo>hallo) retourneer Integer.MIN_VALUE;  // Als de subarray slechts één element bevat, retourneert u het // element if (lo == hi) retourneert a[lo];  int midden = (lo + hi) / 2;  // Haal het maximale element uit de linkerhelft int leftMax = findMax(a, lo, mid);  // Haal het maximale element uit de rechterhelft int rightMax = findMax(a, mid + 1, hi);  // Retourneer het maximale element van links en // rechterhelft retourneer Math.max(leftMax, rightMax); }>

# Function to find the maximum number # in a given array. def find_max(a, lo, hi): # If lo becomes greater than hi, then return minimum # integer possible if lo>hi: return float('-inf') # Als de subarray maar één element heeft, retourneer dan het # element als lo == hi: return a[lo] mid = (lo + hi) // 2 # Haal het maximum element uit de linkerhelft left_max = find_max(a, lo, mid) # Haal het maximale element uit de rechterhelft right_max = find_max(a, mid + 1, hi) # Retourneer het maximale element van links en rechts # half return max (links_max, rechts_max)>

// Function to find the maximum number // in a given array. static int FindMax(int[] a, int lo, int hi) {  // If lo becomes greater than hi, then return  // minimum integer possible  if (lo>hallo) return int.MinValue;  // Als de subarray slechts één element bevat, retourneert u het // element if (lo == hi) retourneert a[lo];  int midden = (lo + hi) / 2;  // Haal het maximale element uit de linkerhelft int leftMax = FindMax(a, lo, mid);  // Haal het maximale element uit de rechterhelft int rightMax = FindMax(a, mid + 1, hi);  // Retourneer het maximale element van links en // rechterhelft retourneer Math.Max(leftMax, rightMax); }>

// Function to find the maximum number // in a given array. function findMax(a, lo, hi) {  // If lo becomes greater than hi, then return minimum  // integer possible  if (lo>hallo) retourneert nummer.MIN_VALUE;  // Als de subarray slechts één element bevat, retourneert u het // element if (lo === hi) retourneert a[lo];  const mid = Math.floor((lo + hi) / 2);  // Haal het maximale element uit de linkerhelft const leftMax = findMax(a, lo, mid);  // Haal het maximale element uit de rechterhelft const rightMax = findMax(a, mid + 1, hi);  // Retourneer het maximale element van links en rechts // halve return Math.max(leftMax, rightMax); }>

2. Het minimumelement in de array vinden:

Op dezelfde manier kunnen we het Divide and Conquer-algoritme gebruiken om het minimumelement in de array te vinden door de array in twee subarrays van gelijke grootte te verdelen, en het minimum van die twee individuele helften te vinden door ze opnieuw in twee kleinere helften te verdelen. Dit wordt gedaan totdat we subarrays van grootte 1 bereiken. Nadat we de elementen hebben bereikt, retourneren we het minimumelement en combineren we de subarrays door het minimum in elke subarray terug te geven.

3. Sortering samenvoegen:

We kunnen het Divide and Conquer-algoritme gebruiken om de array in oplopende of aflopende volgorde te sorteren door de array in kleinere subarrays te verdelen, de kleinere subarrays te sorteren en vervolgens de gesorteerde arrays samen te voegen om de originele array te sorteren.

Complexiteitsanalyse van verdeel en heers-algoritme:

T(n) = aT(n/b) + f(n), waarbij n = grootte van invoer a = aantal subproblemen in de recursie n/b = grootte van elk subprobleem. Er wordt aangenomen dat alle deelproblemen even groot zijn. f(n) = kosten van het werk dat buiten de recursieve aanroep wordt gedaan, inclusief de kosten voor het delen van het probleem en de kosten voor het samenvoegen van de oplossingen

Toepassingen van het verdeel en heers-algoritme:

Hieronder volgen enkele standaardalgoritmen die het Divide and Conquer-algoritme volgen:

• Snel sorteren is een sorteeralgoritme dat een draaielement kiest en de array-elementen herschikt, zodat alle elementen die kleiner zijn dan het gekozen draaielement naar de linkerkant van het draaipunt bewegen, en alle grotere elementen naar de rechterkant. Ten slotte sorteert het algoritme recursief de subarrays links en rechts van het draaielement.
• Sortering samenvoegen is ook een sorteeralgoritme. Het algoritme verdeelt de array in twee helften, sorteert ze recursief en voegt uiteindelijk de twee gesorteerde helften samen.
• Dichtstbijzijnde paar punten Het probleem is om het dichtstbijzijnde paar punten te vinden in een reeks punten in het x-y-vlak. Het probleem kan in O(n^2) tijd worden opgelost door de afstanden van elk paar punten te berekenen en de afstanden te vergelijken om het minimum te vinden. Het verdeel en heers-algoritme lost het probleem op in O(N log N) tijd.
• Het algoritme van Strassen is een efficiënt algoritme om twee matrices te vermenigvuldigen. Een eenvoudige methode om twee matrices te vermenigvuldigen heeft 3 geneste lussen nodig en is O(n^3). Het algoritme van Strassen vermenigvuldigt twee matrices in O(n^2,8974) tijd.
• Cooley-Tukey Fast Fourier Transform (FFT) -algoritme is het meest gebruikelijke algoritme voor FFT. Het is een verdeel en heers-algoritme dat werkt in O(N log N) tijd.
• Karatsuba-algoritme voor snelle vermenigvuldiging doet de vermenigvuldiging van twee binaire strings in O(n^1,59) waarbij n de lengte van de binaire reeks is.

Voordelen van het verdeel en heers-algoritme:

• Moeilijke problemen oplossen: Verdeel en heers-techniek is een hulpmiddel om moeilijke problemen conceptueel op te lossen. bijv. Puzzel Toren van Hanoi. Het vereist een manier om het probleem op te delen in deelproblemen, deze allemaal als individuele gevallen op te lossen en vervolgens deelproblemen te combineren tot het oorspronkelijke probleem.
• Algoritme-efficiëntie: Het verdeel-en-heers-algoritme helpt vaak bij het ontdekken van efficiënte algoritmen. Het is de sleutel tot algoritmen zoals Quick Sort en Merge Sort, en snelle Fourier-transformaties.
• Parallellisme: Normaal gesproken worden Divide and Conquer-algoritmen gebruikt in machines met meerdere processors met systemen met gedeeld geheugen, waarbij de gegevenscommunicatie tussen processors niet van tevoren hoeft te worden gepland, omdat verschillende subproblemen op verschillende processors kunnen worden uitgevoerd.
• Geheugentoegang: Deze algoritmen maken uiteraard efficiënt gebruik van geheugencaches. Omdat de subproblemen klein genoeg zijn om in de cache te worden opgelost zonder gebruik te maken van het langzamere hoofdgeheugen. Elk algoritme dat cache efficiënt gebruikt, wordt cache-onbewust genoemd.

Nadelen van het verdeel en heers-algoritme:

• Bovengronds: Het proces waarbij het probleem in deelproblemen wordt opgedeeld en vervolgens de oplossingen worden gecombineerd, kan extra tijd en middelen vergen. Deze overhead kan aanzienlijk zijn bij problemen die al relatief klein zijn of die een eenvoudige oplossing hebben.
• Complexiteit: Het opdelen van een probleem in kleinere deelproblemen kan de complexiteit van de algehele oplossing vergroten. Dit geldt met name wanneer de deelproblemen onderling afhankelijk zijn en in een specifieke volgorde moeten worden opgelost.
• Moeilijkheidsgraad van implementatie: Sommige problemen zijn moeilijk op te delen in kleinere deelproblemen of vereisen daarvoor een complex algoritme. In deze gevallen kan het een uitdaging zijn om een ​​verdeel-en-heers-oplossing te implementeren.
• Geheugenbeperkingen: Bij het werken met grote datasets kunnen de geheugenvereisten voor het opslaan van de tussenresultaten van de deelproblemen een beperkende factor worden.

Veelgestelde vragen (FAQ's) over het verdeel en heers-algoritme:

1. Wat is het Verdeel en Heers-algoritme?

Verdeel en heers is een probleemoplossende techniek waarbij een probleem wordt opgedeeld in kleinere, beter beheersbare deelproblemen. Deze subproblemen worden recursief opgelost en vervolgens worden hun oplossingen gecombineerd om het oorspronkelijke probleem op te lossen.

inclusief c-programmering

2. Wat zijn de belangrijkste stappen van het Verdeel en Heers-algoritme?

De belangrijkste stappen zijn:

Verdeling : Verdeel het probleem in kleinere deelproblemen.

Veroveren : Los de deelproblemen recursief op.

Combineren : Voeg de oplossingen van de deelproblemen samen of combineer ze om de oplossing voor het oorspronkelijke probleem te verkrijgen.

int in tekenreeks

3. Wat zijn enkele voorbeelden van problemen die zijn opgelost met Verdeel en Heers?

Verdeel en heers-algoritme wordt gebruikt in sorteeralgoritmen zoals Merge Sort en Quick Sort, het vinden van het dichtstbijzijnde paar punten, het algoritme van Strassen, enz.

4. Hoe maakt Merge Sort gebruik van de Verdeel en Heers-aanpak?

Merge Sort verdeelt de array in twee helften, sorteert elke helft recursief en voegt vervolgens de gesorteerde helften samen om de uiteindelijk gesorteerde array te produceren.

5. Wat is de tijdscomplexiteit van verdeel-en-heers-algoritmen?

De tijdscomplexiteit varieert afhankelijk van het specifieke probleem en de manier waarop het wordt geïmplementeerd. Over het algemeen hebben veel verdeel-en-heers-algoritmen een tijdscomplexiteit van O(n log n) of beter.

6. Kunnen verdeel-en-heers-algoritmen worden geparallelliseerd?

Ja, verdeel en heers-algoritmen zijn vaak van nature parallelleerbaar omdat onafhankelijke deelproblemen gelijktijdig kunnen worden opgelost. Dit maakt ze geschikt voor parallelle computeromgevingen.

7. Wat zijn enkele strategieën voor het kiezen van het basisscenario in verdeel-en-heers-algoritmen?

Het basisscenario moet eenvoudig genoeg zijn om direct op te lossen, zonder verdere onderverdeling. Het wordt vaak gekozen op basis van de kleinste invoergrootte, waarbij het probleem triviaal kan worden opgelost.

8. Zijn er nadelen of beperkingen aan het gebruik van Verdeel en Heers?

Hoewel Verdeel en Heers voor veel problemen tot efficiënte oplossingen kan leiden, is het wellicht niet geschikt voor alle soorten problemen. Overhead als gevolg van recursie en het combineren van oplossingen kan ook een probleem zijn bij zeer grote problemen.

9. Hoe analyseer je de ruimtecomplexiteit van Divide and Conquer-algoritmen?

De complexiteit van de ruimte hangt af van factoren zoals de recursiediepte en de hulpruimte die nodig is voor het combineren van oplossingen. Bij het analyseren van de complexiteit van de ruimte wordt doorgaans rekening gehouden met de ruimte die door elke recursieve oproep wordt gebruikt.

10. Wat zijn enkele veel voorkomende voordelen van het Verdeel en Heers-algoritme?

Verdeel en heers-algoritme heeft tal van voordelen. Sommigen van hen omvatten:

• Moeilijke problemen oplossen
• Algoritme-efficiëntie
• Parallellisme
• Geheugentoegang

Verdeel en heers is een populaire algoritmische techniek in de computerwetenschap waarbij een probleem wordt opgedeeld in kleinere deelproblemen, elk deelprobleem afzonderlijk wordt opgelost en vervolgens de oplossingen voor de deelproblemen worden gecombineerd om het oorspronkelijke probleem op te lossen. Het basisidee achter deze techniek is om een ​​probleem op te delen in kleinere, beter beheersbare deelproblemen die gemakkelijker kunnen worden opgelost.