Splitt og hersk Algoritme er en problemløsningsteknikk som brukes til å løse problemer ved å dele hovedproblemet inn i delproblemer, løse dem individuelt og deretter slå dem sammen for å finne løsningen på det opprinnelige problemet. I denne artikkelen skal vi diskutere hvordan Divide and Conquer Algorithm er nyttig og hvordan vi kan bruke den til å løse problemer.

Innholdsfortegnelse

• Definisjon av Divide and Conquer-algoritme
• Arbeid med Divide and Conquer-algoritmen
• Kjennetegn på Divide and Conquer-algoritmen
• Eksempler på Divide and Conquer-algoritmen
• Kompleksitetsanalyse av Divide and Conquer-algoritmen
• Anvendelser av Divide and Conquer-algoritmen
• Fordeler med Divide and Conquer-algoritmen
• Ulemper med Divide and Conquer-algoritmen

Splitt og hersk Algoritmedefinisjon:

Divide and Conquer-algoritmen innebærer å dele opp et større problem i mindre delproblemer, løse dem uavhengig, og deretter kombinere deres løsninger for å løse det opprinnelige problemet. Grunnideen er å rekursivt dele problemet inn i mindre delproblemer til de blir enkle nok til å løses direkte. Når løsningene på delproblemene er oppnådd, kombineres de for å produsere den samlede løsningen.

Arbeid med splitt og hersk-algoritmen:

Divide and Conquer-algoritmen kan deles inn i tre trinn: Dele opp , Erobre og Slå sammen .

1. Del opp:

• Bryt ned det opprinnelige problemet i mindre delproblemer.
• Hvert delproblem skal representere en del av det overordnede problemet.
• Målet er å dele opp problemet til ingen ytterligere deling er mulig.

2. Erobre:

• Løs hvert av de mindre delproblemene individuelt.
• Hvis et delproblem er lite nok (ofte referert til som basistilfellet), løser vi det direkte uten ytterligere rekursjon.
• Målet er å finne løsninger på disse delproblemene selvstendig.

3. Slå sammen:

• Kombiner delproblemene for å få den endelige løsningen på hele problemet.
• Når de mindre delproblemene er løst, kombinerer vi rekursivt løsningene deres for å få løsningen på større problem.
• Målet er å formulere en løsning for det opprinnelige problemet ved å slå sammen resultatene fra deloppgavene.

Kjennetegn ved Divide and Conquer-algoritmen:

Divide and Conquer Algorithm innebærer å bryte ned et problem i mindre, mer håndterbare deler, løse hver del individuelt, og deretter kombinere løsningene for å løse det opprinnelige problemet. Egenskapene til Divide and Conquer-algoritmen er:

• Dele problemet : Det første trinnet er å dele opp problemet i mindre, mer håndterbare delproblemer. Denne inndelingen kan gjøres rekursivt til delproblemene blir enkle nok til å løse direkte.
• Uavhengighet av delproblemer : Hvert delproblem skal være uavhengig av de andre, noe som betyr at løsning av ett delproblem ikke er avhengig av løsningen til et annet. Dette gir mulighet for parallell behandling eller samtidig utførelse av delproblemer, noe som kan føre til effektivitetsgevinster.
• Erobre hvert delproblem : Når de er delt, løses deloppgavene individuelt. Dette kan innebære å bruke den samme skille og hersk-tilnærmingen rekursivt til delproblemene blir enkle nok til å løse direkte, eller det kan innebære å bruke en annen algoritme eller teknikk.
• Kombinere løsninger : Etter å ha løst underoppgavene, kombineres løsningene deres for å få løsningen på det opprinnelige problemet. Dette kombinasjonstrinnet skal være relativt effektivt og greit, da løsningene på delproblemene bør utformes for å passe sømløst sammen.

Eksempler på Divide and Conquer-algoritme:

1. Finne det maksimale elementet i matrisen:

Vi kan bruke Divide and Conquer-algoritmen for å finne det maksimale elementet i arrayen ved å dele arrayet i to like store underarrays, finne maksimum av disse to individuelle halvdelene ved å dele dem i to mindre halvdeler igjen. Dette gjøres til vi når subarrays av størrelse 1. Etter å ha nådd elementene returnerer vi maksimumselementet og kombinerer subarrays ved å returnere maksimum i hver subarray.

// 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>hei) returner INT_MIN;  // Hvis undermatrisen bare har ett element, returner //-elementet if (lo == hi) returner a[lo];  int mid = (lo + hei) / 2;  // Få maksimumselementet fra venstre halvdel int leftMax = findMax(a, lo, mid);  // Få maksimumselementet fra høyre halvdel int rightMax = findMax(a, mid + 1, hi);  // Returner maksimumselementet fra venstre og høyre // 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>hei) returner heltall.MIN_VALUE;  // Hvis undermatrisen bare har ett element, returner //-elementet if (lo == hi) returner a[lo];  int mid = (lo + hei) / 2;  // Få maksimumselementet fra venstre halvdel int leftMax = findMax(a, lo, mid);  // Få maksimumselementet fra høyre halvdel int rightMax = findMax(a, mid + 1, hi);  // Returner maksimumselementet fra venstre og // høyre halv return 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') # Hvis subarrayen bare har ett element, returner # elementet hvis lo == hi: return a[lo] mid = (lo + hi) // 2 # Få maksimum element fra venstre halvdel left_max = find_max(a, lo, mid) # Få maksimumselementet fra høyre halvdel right_max = find_max(a, mid + 1, hi) # Returner maksimumselementet fra venstre og høyre # halv retur maks (venstre_maks, høyre_maks)>

// 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>hei) return int.MinValue;  // Hvis undermatrisen bare har ett element, returner //-elementet if (lo == hi) returner a[lo];  int mid = (lo + hei) / 2;  // Få maksimumselementet fra venstre halvdel int leftMax = FindMax(a, lo, mid);  // Få maksimumselementet fra høyre halvdel int rightMax = FindMax(a, mid + 1, hi);  // Returner maksimumselementet fra venstre og // høyre halv return 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>hei) returner nummer.MIN_VALUE;  // Hvis undermatrisen bare har ett element, returner //-elementet if (lo === hi) returner a[lo];  const mid = Math.floor((lo + hei) / 2);  // Få maksimumselementet fra venstre halvdel const leftMax = findMax(a, lo, mid);  // Få maksimumselementet fra høyre halvdel const rightMax = findMax(a, mid + 1, hi);  // Returner maksimumselementet fra venstre og høyre // half return Math.max(leftMax, rightMax); }>

2. Finn minimumselementet i matrisen:

På samme måte kan vi bruke Divide and Conquer Algorithm for å finne minimumselementet i matrisen ved å dele matrisen i to like store subarrays, finne minimum av de to individuelle halvdelene ved å dele dem i to mindre halvdeler igjen. Dette gjøres til vi når subarrays av størrelse 1. Etter å ha nådd elementene returnerer vi minimumselementet og kombinerer subarrays ved å returnere minimum i hver subarray.

3. Slå sammen sortering:

Vi kan bruke Divide and Conquer Algorithm for å sortere matrisen i stigende eller synkende rekkefølge ved å dele opp matrisen i mindre subarrays, sortere de mindre subarrayene og deretter slå sammen de sorterte matrisene for å sortere den originale matrisen.

Kompleksitetsanalyse av Divide and Conquer-algoritmen:

T(n) = aT(n/b) + f(n), hvor n = størrelsen på input a = antall delproblemer i rekursjonen n/b = størrelsen på hver deloppgave. Alle deloppgaver antas å ha samme størrelse. f(n) = kostnaden for arbeidet utført utenfor den rekursive samtalen, som inkluderer kostnaden for å dele problemet og kostnaden for å slå sammen løsningene

Anvendelser av Divide and Conquer-algoritmen:

Følgende er noen standardalgoritmer som følger Divide and Conquer-algoritmen:

• Quicksort er en sorteringsalgoritme som plukker et pivotelement og omorganiserer matriseelementene slik at alle elementer som er mindre enn det valgte pivotelementet flyttes til venstre side av pivoten, og alle større elementer flyttes til høyre side. Til slutt sorterer algoritmen rekursivt subarrayene til venstre og høyre for pivotelementet.
• Slå sammen sortering er også en sorteringsalgoritme. Algoritmen deler matrisen i to halvdeler, sorterer dem rekursivt og slår til slutt sammen de to sorterte halvdelene.
• Nærmeste poengpar Problemet er å finne det nærmeste paret av punkter i et sett med punkter i x-y-planet. Problemet kan løses i O(n^2) tid ved å beregne avstandene til hvert par av punkter og sammenligne avstandene for å finne minimum. Divide and Conquer-algoritmen løser problemet i O(N log N) tid.
• Strassens algoritme er en effektiv algoritme for å multiplisere to matriser. En enkel metode for å multiplisere to matriser trenger 3 nestede løkker og er O(n^3). Strassens algoritme multipliserer to matriser i O(n^2.8974) tid.
• Cooley–Tukey Fast Fourier Transform (FFT) algoritme er den vanligste algoritmen for FFT. Det er en del og hersk algoritme som fungerer i O(N log N) tid.
• Karatsuba-algoritme for rask multiplikasjon utfører multiplikasjonen av to binære strenger i O(n^1,59) hvor n er lengden på binær streng.

Fordeler med Divide and Conquer-algoritmen:

• Løse vanskelige problemer: Del og hersk-teknikk er et verktøy for å løse vanskelige problemer konseptuelt. f.eks. Tower of Hanoi puslespill. Det krever en måte å dele opp problemet i delproblemer, og løse alle som enkelttilfeller og deretter kombinere delproblemer med det opprinnelige problemet.
• Algoritmeeffektivitet: Del-og-hersk-algoritmen hjelper ofte med å finne effektive algoritmer. Det er nøkkelen til algoritmer som Quick Sort og Merge Sort, og raske Fourier-transformasjoner.
• Parallellisme: Normalt brukes Divide and Conquer-algoritmer i maskiner med flere prosessorer som har delt minnesystemer der kommunikasjonen av data mellom prosessorer ikke trenger å planlegges på forhånd, fordi distinkte underproblemer kan utføres på forskjellige prosessorer.
• Minnetilgang: Disse algoritmene gjør naturlig nok en effektiv bruk av minnebuffere. Siden underproblemene er små nok til å løses i cache uten å bruke hovedminnet som er tregere. Enhver algoritme som bruker cache effektivt kalles cache oblivious.

Ulemper med Divide and Conquer-algoritmen:

• Overhead: Prosessen med å dele opp problemet i delproblemer og deretter kombinere løsningene kan kreve ekstra tid og ressurser. Denne overheaden kan være betydelig for problemer som allerede er relativt små eller som har en enkel løsning.
• Kompleksitet: Å dele opp et problem i mindre delproblemer kan øke kompleksiteten til den samlede løsningen. Dette gjelder spesielt når delproblemene er gjensidig avhengige og må løses i en bestemt rekkefølge.
• Vanskeligheter med implementering: Noen problemer er vanskelige å dele inn i mindre delproblemer eller krever en kompleks algoritme for å gjøre det. I disse tilfellene kan det være utfordrende å implementere en skille og hersk-løsning.
• Minnebegrensninger: Ved arbeid med store datasett kan minnekravene for lagring av mellomresultatene av delproblemene bli en begrensende faktor.

Ofte stilte spørsmål (FAQs) om Divide and Conquer-algoritmen:

1. Hva er Divide and Conquer-algoritmen?

Divide and Conquer er en problemløsningsteknikk der et problem deles inn i mindre, mer håndterbare delproblemer. Disse delproblemene løses rekursivt, og deretter kombineres løsningene deres for å løse det opprinnelige problemet.

2. Hva er de viktigste trinnene i Divide and Conquer-algoritmen?

Hovedtrinnene er:

Dele opp : Del opp problemet i mindre delproblemer.

Erobre : Løs delproblemene rekursivt.

Kombinere : Slå sammen eller kombiner løsningene til deloppgavene for å få løsningen på det opprinnelige problemet.

3. Hva er noen eksempler på problemer løst ved hjelp av Divide and Conquer?

Divide and Conquer Algorithm brukes til å sortere algoritmer som Merge Sort og Quick Sort, finne nærmeste poengpar, Strassens algoritme, etc.

4. Hvordan bruker Merge Sort Divide and Conquer-tilnærmingen?

Merge Sort deler matrisen i to halvdeler, sorterer rekursivt hver halvdel, og slår deretter sammen de sorterte halvdelene for å produsere den endelige sorterte matrisen.

5. Hva er tidskompleksiteten til Divide and Conquer-algoritmer?

Tidskompleksiteten varierer avhengig av det spesifikke problemet og hvordan det implementeres. Generelt har mange Divide and Conquer-algoritmer en tidskompleksitet på O(n log n) eller bedre.

6. Kan Divide and Conquer-algoritmer parallelliseres?

Ja, Divide and Conquer-algoritmer er ofte naturlig parallelliserbare fordi uavhengige delproblemer kan løses samtidig. Dette gjør dem egnet for parallelle datamiljøer.

7. Hva er noen strategier for å velge grunntilfelle i Divide and Conquer-algoritmer?

Grunnlaget skal være enkelt nok til å løse direkte, uten ytterligere oppdeling. Det er ofte valgt basert på den minste inngangsstørrelsen der problemet kan løses trivielt.

8. Er det noen ulemper eller begrensninger ved bruk av Divide and Conquer?

Mens Divide and Conquer kan føre til effektive løsninger for mange problemer, er det kanskje ikke egnet for alle problemtyper. Overhead fra rekursjon og å kombinere løsninger kan også være en bekymring for svært store problemstørrelser.

9. Hvordan analyserer du romkompleksiteten til Divide and Conquer-algoritmer?

Romkompleksiteten avhenger av faktorer som rekursjonsdybden og hjelpeplassen som kreves for å kombinere løsninger. Å analysere plasskompleksitet innebærer vanligvis å vurdere plassen som brukes av hvert rekursivt anrop.

instansierer java

10. Hva er noen vanlige fordeler med Divide and Conquer Algorithm?

Divide and Conquer-algoritmen har mange fordeler. Noen av dem inkluderer:

• Løse vanskelige problemer
• Algoritme effektivitet
• Parallellisme
• Minnetilgang

Divide and Conquer er en populær algoritmisk teknikk innen informatikk som innebærer å bryte ned et problem i mindre delproblemer, løse hvert delproblem uavhengig, og deretter kombinere løsningene på delproblemene for å løse det opprinnelige problemet. Grunntanken bak denne teknikken er å dele et problem i mindre, mer håndterbare delproblemer som kan løses lettere.