TechCodeview

Verdeel en heers is een algoritmisch patroon. Bij algoritmische methoden is het de bedoeling om een ​​dispuut over een enorme input te nemen, de input in kleine stukjes te verdelen, het probleem op elk van de kleine stukjes te beslissen en vervolgens de oplossingen in stukjes samen te voegen tot een globale oplossing. Dit mechanisme om het probleem op te lossen wordt de Verdeel en Heers Strategie genoemd.

Het verdeel en heers-algoritme bestaat uit een geschil met behulp van de volgende drie stappen.

Verdelinghet oorspronkelijke probleem in een reeks subproblemen.Veroveren:Los elk deelprobleem afzonderlijk en recursief op.Combineren:Voeg de oplossingen van de deelproblemen samen om de oplossing voor het hele probleem te krijgen.

Over het algemeen kunnen we de verdeel en heers aanpak in een proces van drie stappen.

Voorbeelden: De specifieke computeralgoritmen zijn gebaseerd op de Divide & Conquer-aanpak:

1. Maximaal en minimaal probleem
2. Binaire zoekopdracht
3. Sorteren (samenvoegen, snel sorteren)
4. Toren van Hanoi.

Fundamenteel van de verdeel-en-heersstrategie:

Er zijn twee fundamentele aspecten van de verdeel-en-heers-strategie:

1. Relationele formule
2. Conditie stoppen

1. Relationele formule: Het is de formule die we genereren op basis van de gegeven techniek. Na het genereren van de formule passen we de D&C-strategie toe, dat wil zeggen dat we het probleem recursief opsplitsen en de kapotte subproblemen oplossen.

2. Stopvoorwaarde: Wanneer we het probleem oplossen met behulp van de verdeel-en-heersstrategie, moeten we weten voor hoeveel tijd we de verdeel-en-heersstrategie moeten toepassen. Dus de voorwaarde waarbij de noodzaak om onze recursiestappen van D&C te stoppen, wordt stopvoorwaarde genoemd.

Toepassingen van de verdeel en heers-aanpak:

De volgende algoritmen zijn gebaseerd op het concept van de Verdeel en Heers-techniek:

Binaire zoekopdracht:Het binaire zoekalgoritme is een zoekalgoritme, ook wel half-interval zoeken of logaritmisch zoeken genoemd. Het werkt door de doelwaarde te vergelijken met het middelste element dat in een gesorteerde array bestaat. Als de waarde na het maken van de vergelijking verschilt, zal de helft die het doelwit niet kan bevatten uiteindelijk worden geëlimineerd, gevolgd door het voortzetten van de zoektocht naar de andere helft. We zullen opnieuw naar het middelste element kijken en dit vergelijken met de streefwaarde. Het proces blijft zich herhalen totdat de doelwaarde is bereikt. Als we na het beëindigen van de zoekopdracht vaststellen dat de andere helft leeg is, kan worden geconcludeerd dat het doel niet in de array aanwezig is.Snel sorteren:Het is het meest efficiënte sorteeralgoritme, ook wel partitie-uitwisselingssortering genoemd. Het begint met het selecteren van een draaiwaarde uit een array, gevolgd door het verdelen van de rest van de array-elementen in twee sub-arrays. De partitie wordt gemaakt door elk van de elementen te vergelijken met de draaiwaarde. Het vergelijkt of het element een grotere of kleinere waarde heeft dan het draaipunt en sorteert vervolgens de arrays recursief.Sortering samenvoegen:Het is een sorteeralgoritme dat een array sorteert door vergelijkingen te maken. Het begint met het verdelen van een array in subarrays en sorteert ze vervolgens recursief. Nadat het sorteren is voltooid, worden ze weer samengevoegd.Dichtstbijzijnde paar punten:Het is een probleem van computationele meetkunde. Dit algoritme legt de nadruk op het vinden van het dichtstbijzijnde paar punten in een metrische ruimte, gegeven n punten, zodat de afstand tussen het paar punten minimaal moet zijn.Het algoritme van Strassen:Het is een algoritme voor matrixvermenigvuldiging, vernoemd naar Volker Strassen. Het is gebleken dat het veel sneller is dan het traditionele algoritme bij het werken met grote matrices.Cooley-Tukey Fast Fourier Transform (FFT)-algoritme:Het Fast Fourier Transform-algoritme is vernoemd naar JW Cooley en John Turkey. Het volgt de verdeel en heersbenadering en legt een complexiteit van O(nlogn) op.Karatsuba-algoritme voor snelle vermenigvuldiging:Het is een van de snelste vermenigvuldigingsalgoritmen van de traditionele tijd, uitgevonden door Anatoly Karatsuba eind 1960 en gepubliceerd in 1962. Het vermenigvuldigt twee getallen van n cijfers op een zodanige manier door het terug te brengen tot maximaal één cijfer.

Voordelen van verdeel en heers

• Verdeel en heers hebben de neiging om met succes een van de grootste problemen op te lossen, zoals de Toren van Hanoi, een wiskundige puzzel. Het is een uitdaging om ingewikkelde problemen op te lossen waarvoor je geen basisidee hebt, maar met behulp van de verdeel-en-heers-aanpak heeft het de inspanning verminderd omdat het werkt aan het verdelen van het hoofdprobleem in twee helften en deze vervolgens recursief oplost. Dit algoritme is veel sneller dan andere algoritmen.
• Het maakt efficiënt gebruik van cachegeheugen zonder veel ruimte in beslag te nemen, omdat het eenvoudige deelproblemen binnen het cachegeheugen oplost in plaats van toegang te krijgen tot het langzamere hoofdgeheugen.
• Het is bekwamer dan die van zijn tegenhanger Brute Force-techniek.
• Omdat deze algoritmen parallellisme tegengaan, zijn er geen wijzigingen nodig en wordt het afgehandeld door systemen die parallelle verwerking bevatten.

Nadelen van verdeel en heers

• Omdat de meeste algoritmen zijn ontworpen door recursie te integreren, is er een hoog geheugenbeheer nodig.
• Een expliciete stapel kan de ruimte te veel gebruiken.
• Het systeem kan zelfs crashen als de recursie rigoureus groter wordt uitgevoerd dan de stapel die in de CPU aanwezig is.