Divide and Conquer är ett algoritmiskt mönster. I algoritmiska metoder är designen att ta en tvist om en enorm input, dela in input i mindre bitar, avgöra problemet på var och en av de små bitarna och sedan slå samman de bitvisa lösningarna till en global lösning. Denna mekanism för att lösa problemet kallas Divide & Conquer-strategin.

Divide and Conquer-algoritmen består av en tvist med följande tre steg.

Dela uppdet ursprungliga problemet till en uppsättning delproblem.Erövra:Lös varje delproblem individuellt, rekursivt.Kombinera:Sätt ihop lösningarna på delproblemen för att få lösningen på hela problemet.

I allmänhet kan vi följa söndra och erövra tillvägagångssätt i en trestegsprocess.

Exempel: De specifika datoralgoritmerna är baserade på Divide & Conquer-metoden:

1. Maximalt och minimalt problem
2. Binär sökning
3. Sortering (sammanfoga sortering, snabb sortering)
4. Hanois torn.

Fundamental of Divide & Conquer-strategi:

Det finns två grundläggande för Divide & Conquer-strategin:

1. Relationsformel
2. Stopptillstånd

1. Relationsformel: Det är formeln som vi genererar från den givna tekniken. Efter generering av Formel tillämpar vi D&C Strategy, dvs vi bryter problemet rekursivt och löser de trasiga delproblemen.

2. Stopptillstånd: När vi bryter problemet med Divide & Conquer Strategy, då måste vi veta att under hur lång tid måste vi tillämpa divide & Conquer. Så tillståndet där behovet av att stoppa våra rekursionssteg av D&C kallas Stopping Condition.

Tillämpningar av Divide and Conquer-metoden:

Följande algoritmer är baserade på konceptet Divide and Conquer-tekniken:

Binär sökning:Den binära sökalgoritmen är en sökalgoritm, som också kallas en halvintervallssökning eller logaritmisk sökning. Det fungerar genom att jämföra målvärdet med mittelementet som finns i en sorterad array. Efter att ha gjort jämförelsen, om värdet skiljer sig, kommer halvan som inte kan innehålla målet så småningom att elimineras, följt av att fortsätta sökningen på den andra halvan. Vi kommer återigen att överväga mittelementet och jämföra det med målvärdet. Processen fortsätter att upprepas tills målvärdet uppnås. Om vi ​​fann att den andra halvan var tom efter att sökningen avslutats, kan man dra slutsatsen att målet inte finns i arrayen.Snabbsort:Det är den mest effektiva sorteringsalgoritmen, som också är känd som partitionsutbytessortering. Det börjar med att välja ett pivotvärde från en array följt av att dela upp resten av arrayelementen i två sub-arrayer. Partitionen görs genom att jämföra vart och ett av elementen med pivotvärdet. Den jämför om elementet har ett större eller lägre värde än pivoten och sorterar sedan arrayerna rekursivt.Slå samman sortering:Det är en sorteringsalgoritm som sorterar en array genom att göra jämförelser. Den börjar med att dela upp en array i sub-array och sorterar sedan rekursivt var och en av dem. När sorteringen är klar slår den ihop dem igen.Närmaste poängpar:Det är ett problem med beräkningsgeometri. Denna algoritm betonar att ta reda på det närmaste paret av punkter i ett metriskt utrymme, givet n punkter, så att avståndet mellan paret av punkter bör vara minimalt.Strassens algoritm:Det är en algoritm för matrismultiplikation, som är uppkallad efter Volker Strassen. Den har visat sig vara mycket snabbare än den traditionella algoritmen när den fungerar på stora matriser.Cooley-Tukey Fast Fourier Transform (FFT) algoritm:Algoritmen för snabb Fouriertransform är uppkallad efter J. W. Cooley och John Turkey. Den följer Divide and Conquer-metoden och inför en komplexitet av O(nlogn).Karatsuba-algoritm för snabb multiplikation:Det är en av den traditionella tidens snabbaste multiplikationsalgoritmer, uppfann av Anatoly Karatsuba i slutet av 1960 och publicerades 1962. Den multiplicerar två n-siffriga tal på ett sådant sätt genom att reducera dem till högst ensiffriga.

Fördelar med Divide and Conquer

• Divide and Conquer tenderar att framgångsrikt lösa ett av de största problemen, som Tower of Hanoi, ett matematiskt pussel. Det är utmanande att lösa komplicerade problem som man inte har någon grundläggande idé om, men med hjälp av dela och erövra-metoden har det minskat ansträngningen då man arbetar med att dela upp huvudproblemet i två halvor och sedan lösa dem rekursivt. Denna algoritm är mycket snabbare än andra algoritmer.
• Den använder cacheminnet effektivt utan att ta upp mycket utrymme eftersom det löser enkla delproblem i cacheminnet istället för att komma åt det långsammare huvudminnet.
• Den är mer skicklig än den i sin motsvarighet Brute Force-teknik.
• Eftersom dessa algoritmer hämmar parallellism, innebär det ingen modifiering och hanteras av system som innehåller parallell bearbetning.

Nackdelar med Divide and Conquer

• Eftersom de flesta av dess algoritmer är designade genom att inkorporera rekursion, så kräver det hög minneshantering.
• En explicit stack kan överanvända utrymmet.
• Det kan till och med krascha systemet om rekursionen utförs kraftigt större än stacken som finns i CPU:n.