TechCodeview

Divide and Conquer er et algoritmisk mønster. I algoritmiske metoder er designet å ta en tvist om et stort input, bryte innspillet i mindre biter, bestemme problemet på hver av de små bitene, og deretter slå sammen de bitvise løsningene til en global løsning. Denne mekanismen for å løse problemet kalles Divide & Conquer-strategien.

Divide and Conquer-algoritmen består av en tvist ved å bruke følgende tre trinn.

Dele oppdet opprinnelige problemet til et sett med delproblemer.Erobre:Løs hvert delproblem individuelt, rekursivt.Kombinere:Sett sammen løsningene av delproblemene for å få løsningen på hele problemet.

Generelt kan vi følge splitt og hersk tilnærming i en tre-trinns prosess.

Eksempler: De spesifikke datamaskinalgoritmene er basert på Divide & Conquer-tilnærmingen:

1. Maksimum og minimum problem
2. Binært søk
3. Sortering (sammenslå sortering, rask sortering)
4. Tårnet i Hanoi.

Fundamental for Divide & Conquer-strategi:

Det er to grunnleggende i Divide & Conquer-strategien:

1. Relasjonsformel
2. Stoppetilstand

1. Relasjonsformel: Det er formelen vi genererer fra den gitte teknikken. Etter generering av Formel bruker vi D&C Strategy, det vil si at vi bryter problemet rekursivt og løser de ødelagte delproblemene.

2. Stopptilstand: Når vi bryter problemet ved å bruke Divide & Conquer Strategy, må vi vite at hvor lang tid vi trenger å bruke divide & conquer. Så tilstanden hvor behovet for å stoppe våre rekursjonstrinn av D&C kalles som Stopping Condition.

Anvendelser av Divide and Conquer-metoden:

Følgende algoritmer er basert på konseptet Divide and Conquer-teknikken:

Binært søk:Den binære søkealgoritmen er en søkealgoritme, som også kalles et halvintervallsøk eller logaritmisk søk. Det fungerer ved å sammenligne målverdien med midtelementet som eksisterer i en sortert matrise. Etter å ha gjort sammenligningen, hvis verdien er forskjellig, vil halvparten som ikke kan inneholde målet til slutt elimineres, etterfulgt av å fortsette søket på den andre halvdelen. Vi vil igjen vurdere midtelementet og sammenligne det med målverdien. Prosessen fortsetter å gjenta seg til målverdien er nådd. Hvis vi fant ut at den andre halvdelen var tom etter endt søket, kan det konkluderes med at målet ikke er tilstede i matrisen.Quicksort:Det er den mest effektive sorteringsalgoritmen, som også er kjent som partisjonsutvekslingssortering. Det starter med å velge en pivotverdi fra en matrise etterfulgt av å dele resten av matriseelementene i to undermatriser. Partisjonen lages ved å sammenligne hvert av elementene med pivotverdien. Den sammenligner om elementet har en større verdi eller mindre verdi enn pivoten og sorterer deretter matrisene rekursivt.Slå sammen sortering:Det er en sorteringsalgoritme som sorterer en matrise ved å gjøre sammenligninger. Den starter med å dele en matrise i undermatrise og sorterer deretter hver av dem rekursivt. Etter at sorteringen er fullført, slår den dem sammen igjen.Nærmeste poengpar:Det er et problem med beregningsgeometri. Denne algoritmen legger vekt på å finne ut det nærmeste paret med punkter i et metrisk rom, gitt n punkter, slik at avstanden mellom punkterparet skal være minimal.Strassens algoritme:Det er en algoritme for matrisemultiplikasjon, som er oppkalt etter Volker Strassen. Den har vist seg å være mye raskere enn den tradisjonelle algoritmen når den fungerer på store matriser.Cooley-Tukey Fast Fourier Transform (FFT) algoritme:Fast Fourier Transform-algoritmen er oppkalt etter J. W. Cooley og John Turkey. Den følger Divide and Conquer-tilnærmingen og pålegger en kompleksitet av O(nlogn).Karatsuba-algoritme for rask multiplikasjon:Det er en av de raskeste multiplikasjonsalgoritmene i den tradisjonelle tiden, oppfunnet av Anatoly Karatsuba på slutten av 1960 og ble publisert i 1962. Den multipliserer to n-sifrede tall på en slik måte ved å redusere den til høyst ensifrede.

Fordeler med Divide and Conquer

• Divide and Conquer har en tendens til å lykkes med å løse et av de største problemene, for eksempel Tower of Hanoi, et matematisk puslespill. Det er utfordrende å løse kompliserte problemer som du ikke har noen grunnleggende idé om, men ved hjelp av skille og hersk-tilnærmingen har det redusert innsatsen ettersom det jobber med å dele hovedproblemet i to halvdeler og deretter løse dem rekursivt. Denne algoritmen er mye raskere enn andre algoritmer.
• Den bruker hurtigbufferminne effektivt uten å ta mye plass fordi den løser enkle underproblemer i hurtigbufferminnet i stedet for å få tilgang til det tregere hovedminnet.
• Den er mer dyktig enn den til motstykket Brute Force-teknikken.
• Siden disse algoritmene hemmer parallellisme, innebærer den ingen modifikasjon og håndteres av systemer som inneholder parallell prosessering.

Ulemper med Divide and Conquer

• Siden de fleste av algoritmene er designet ved å inkludere rekursjon, krever det høy minneadministrasjon.
• En eksplisitt stabel kan overbruke plassen.
• Det kan til og med krasje systemet hvis rekursjonen utføres strengt større enn stabelen som er tilstede i CPU.