Del og hersk Algoritme er en problemløsningsteknik, der bruges til at løse problemer ved at dele hovedproblemet op i delproblemer, løse dem individuelt og derefter flette dem sammen for at finde en løsning på det oprindelige problem. I denne artikel skal vi diskutere, hvordan Divide and Conquer-algoritmen er nyttig, og hvordan vi kan bruge den til at løse problemer.

Indholdsfortegnelse

• Definition af Divide and Conquer-algoritme
• Arbejde med Divide and Conquer-algoritmen
• Karakteristika for Divide and Conquer-algoritmen
• Eksempler på Divide and Conquer-algoritme
• Kompleksitetsanalyse af Divide and Conquer-algoritmen
• Anvendelser af Divide and Conquer-algoritmen
• Fordele ved Divide and Conquer-algoritmen
• Ulemper ved Divide and Conquer-algoritmen

Del og hersk Algoritme definition:

Divide and Conquer-algoritme involverer at dele et større problem op i mindre delproblemer, løse dem selvstændigt og derefter kombinere deres løsninger for at løse det oprindelige problem. Grundideen er rekursivt at opdele problemet i mindre delproblemer, indtil de bliver enkle nok til at kunne løses direkte. Når først løsningerne på delproblemerne er opnået, kombineres de for at producere den overordnede løsning.

Arbejde med Divide and Conquer-algoritmen:

Divide and Conquer-algoritmen kan opdeles i tre trin: Dele , Erobre og Fusionere .

1. Opdel:

• Opdel det oprindelige problem i mindre underopgaver.
• Hvert delproblem skal repræsentere en del af det overordnede problem.
• Målet er at opdele problemet, indtil yderligere opdeling ikke er mulig.

2. Erobre:

• Løs hver af de mindre delproblemer individuelt.
• Hvis et underproblem er lille nok (ofte omtalt som basissagen), løser vi det direkte uden yderligere rekursion.
• Målet er selvstændigt at finde løsninger på disse delproblemer.

3. Flet:

• Kombiner delproblemerne for at få den endelige løsning på hele problemet.
• Når de mindre delproblemer er løst, kombinerer vi rekursivt deres løsninger for at få løsningen på større problem.
• Målet er at formulere en løsning på det oprindelige problem ved at sammenlægge resultaterne fra delopgaverne.

Karakteristika for Divide and Conquer-algoritmen:

Divide and Conquer-algoritmen involverer at nedbryde et problem i mindre, mere håndterbare dele, løse hver del individuelt og derefter kombinere løsningerne for at løse det oprindelige problem. Egenskaberne ved Divide and Conquer-algoritmen er:

• Opdeling af problemet : Det første skridt er at dele problemet op i mindre, mere overskuelige underproblemer. Denne opdeling kan udføres rekursivt, indtil delproblemerne bliver enkle nok til at løse direkte.
• Uafhængighed af delproblemer : Hvert delproblem skal være uafhængigt af de andre, hvilket betyder, at løsning af et delproblem ikke afhænger af løsningen af ​​et andet. Dette giver mulighed for parallel bearbejdning eller samtidig udførelse af delproblemer, hvilket kan føre til effektivitetsgevinster.
• Erobre hvert underproblem : Når de er opdelt, løses delopgaverne individuelt. Dette kan involvere at anvende den samme opdeling og hersk tilgang rekursivt, indtil delproblemerne bliver enkle nok til at løse direkte, eller det kan involvere anvendelse af en anden algoritme eller teknik.
• Kombination af løsninger : Efter at have løst underopgaverne kombineres deres løsninger for at opnå løsningen på det oprindelige problem. Dette kombinationstrin skal være relativt effektivt og ligetil, da løsningerne på delproblemerne bør designes, så de passer problemfrit sammen.

Eksempler på Divide and Conquer-algoritme:

1. Find det maksimale element i arrayet:

Vi kan bruge Divide and Conquer-algoritmen til at finde det maksimale element i arrayet ved at opdele arrayet i to lige store underarrays, finde maksimum af disse to individuelle halvdele ved igen at opdele dem i to mindre halvdele. Dette gøres indtil vi når subarrays af størrelse 1. Efter at have nået elementerne returnerer vi det maksimale element og kombinerer subarrays ved at 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>hej) returner INT_MIN;  // Hvis underarrayet kun har ét element, returnerer du //-elementet if (lo == hi) returnerer a[lo];  int mid = (lo + hej) / 2;  // Få det maksimale element fra venstre halvdel int leftMax = findMax(a, lo, mid);  // Få det maksimale element fra højre halvdel int rightMax = findMax(a, mid + 1, hi);  // Returner det maksimale element fra venstre og højre // 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>hej) returner heltal.MIN_VALUE;  // Hvis underarrayet kun har ét element, returnerer du //-elementet if (lo == hi) returnerer a[lo];  int mid = (lo + hej) / 2;  // Få det maksimale element fra venstre halvdel int leftMax = findMax(a, lo, mid);  // Få det maksimale element fra højre halvdel int rightMax = findMax(a, mid + 1, hi);  // Returner det maksimale element fra venstre og // højre halvdel returner 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 subarrayet kun har ét 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å det maksimale element fra højre halvdel right_max = find_max(a, mid + 1, hi) # Returner det maksimale element fra venstre og højre # halv retur max (venstre_maks, højre_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>hej) returnere int.MinValue;  // Hvis underarrayet kun har ét element, returnerer du //-elementet if (lo == hi) returnerer a[lo];  int mid = (lo + hej) / 2;  // Få det maksimale element fra venstre halvdel int leftMax = FindMax(a, lo, mid);  // Få det maksimale element fra højre halvdel int rightMax = FindMax(a, mid + 1, hi);  // Returner det maksimale element fra venstre og // højre halvdel returner 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>hej) returner nummer.MIN_VALUE;  // Hvis underarrayet kun har ét element, returnerer du // elementet if (lo === hi) returnerer a[lo];  const mid = Math.floor((lo + hej) / 2);  // Få det maksimale element fra venstre halvdel const leftMax = findMax(a, lo, mid);  // Få det maksimale element fra højre halvdel const rightMax = findMax(a, mid + 1, hi);  // Returner det maksimale element fra venstre og højre // half return Math.max(leftMax, rightMax); }>

2. Find minimumselementet i arrayet:

På samme måde kan vi bruge Divide and Conquer Algorithm til at finde minimumselementet i arrayet ved at dele arrayet i to lige store subarrays, finde minimum af disse to individuelle halvdele ved igen at opdele dem i to mindre halvdele. Dette gøres indtil vi når subarrays af størrelse 1. Efter at have nået elementerne returnerer vi minimumselementet og kombinerer subarrays ved at returnere minimum i hver subarray.

3. Flet sortering:

Vi kan bruge Divide and Conquer Algorithm til at sortere arrayet i stigende eller faldende rækkefølge ved at opdele arrayet i mindre underarrays, sortere de mindre underarrays og derefter flette de sorterede arrays for at sortere det originale array.

Kompleksitetsanalyse af opdeling og hersk-algoritme:

T(n) = aT(n/b) + f(n), hvor n = størrelsen af ​​input a = antal delopgaver i rekursionen n/b = størrelsen af ​​hver delopgave. Alle delopgaver antages at have samme størrelse. f(n) = omkostningerne ved det arbejde, der udføres uden for det rekursive kald, som inkluderer omkostningerne ved at opdele problemet og omkostningerne ved at flette løsningerne

Anvendelser af Divide and Conquer-algoritmen:

Følgende er nogle standardalgoritmer, der følger Divide and Conquer-algoritmen:

• Quicksort er en sorteringsalgoritme, der vælger et pivotelement og omarrangerer array-elementerne, så alle elementer, der er mindre end det valgte pivotelement, flytter til venstre side af pivoten, og alle større elementer flytter til højre side. Endelig sorterer algoritmen rekursivt subarrays til venstre og højre for pivotelementet.
• Flet sortering er også en sorteringsalgoritme. Algoritmen opdeler arrayet i to halvdele, sorterer dem rekursivt og slår til sidst de to sorterede halvdele sammen.
• Nærmeste par af punkter Problemet er at finde det nærmeste par punkter i et sæt punkter i x-y-planet. Problemet kan løses i O(n^2) tid ved at beregne afstandene for hvert par af punkter og sammenligne afstandene for at finde minimum. Divide and Conquer-algoritmen løser problemet i O(N log N) tid.
• Strassens algoritme er en effektiv algoritme til at gange to matricer. En simpel metode til at gange to matricer kræver 3 indlejrede løkker og er O(n^3). Strassens algoritme multiplicerer to matricer i O(n^2,8974) tid.
• Cooley–Tukey Fast Fourier Transform (FFT) algoritme er den mest almindelige algoritme for FFT. Det er en opdel og hersk algoritme, som virker i O(N log N) tid.
• Karatsuba algoritme til hurtig multiplikation udfører multiplikationen af ​​to binære strenge i O(n^1,59) hvor n er længden af ​​binær streng.

Fordele ved Divide and Conquer-algoritmen:

• Løsning af vanskelige problemer: Divide and conquer teknik er et værktøj til at løse vanskelige problemer konceptuelt. f.eks. Tower of Hanoi puslespil. Det kræver en måde at opdele problemet i delproblemer og løse dem alle som individuelle sager og derefter kombinere delproblemer med det oprindelige problem.
• Algoritme effektivitet: Opdel-og-hersk-algoritmen hjælper ofte med at finde effektive algoritmer. Det er nøglen til algoritmer som Quick Sort og Merge Sort, og hurtige Fourier-transformationer.
• Parallelisme: Normalt bruges Divide and Conquer-algoritmer i multi-processor maskiner med delt hukommelsessystemer, hvor kommunikationen af ​​data mellem processorer ikke behøver at være planlagt på forhånd, fordi forskellige underproblemer kan udføres på forskellige processorer.
• Hukommelsesadgang: Disse algoritmer gør naturligvis en effektiv brug af hukommelsescaches. Da underproblemerne er små nok til at blive løst i cachen uden at bruge hovedhukommelsen, er den langsommere. Enhver algoritme, der bruger cache effektivt, kaldes cache oblivious.

Ulemper ved Divide and Conquer-algoritmen:

• Overhead: Processen med at opdele problemet i delproblemer og derefter kombinere løsningerne kan kræve ekstra tid og ressourcer. Denne overhead kan være væsentlig for problemer, der allerede er relativt små, eller som har en simpel løsning.
• Kompleksitet: Opdeling af et problem i mindre delproblemer kan øge kompleksiteten af ​​den samlede løsning. Dette gælder især, når delproblemerne er indbyrdes afhængige og skal løses i en bestemt rækkefølge.
• Vanskeligheder ved implementering: Nogle problemer er svære at opdele i mindre delproblemer eller kræver en kompleks algoritme for at gøre det. I disse tilfælde kan det være udfordrende at implementere en skille og hersk-løsning.
• Hukommelsesbegrænsninger: Når man arbejder med store datasæt, kan hukommelseskravene til lagring af delproblemernes mellemresultater blive en begrænsende faktor.

Ofte stillede spørgsmål (FAQs) om Divide and Conquer-algoritmen:

1. Hvad er Divide and Conquer-algoritmen?

Divide and Conquer er en problemløsningsteknik, hvor et problem er opdelt i mindre, mere overskuelige delproblemer. Disse delproblemer løses rekursivt, og derefter kombineres deres løsninger for at løse det oprindelige problem.

2. Hvad er de vigtigste trin involveret i Divide and Conquer-algoritmen?

De vigtigste trin er:

Dele : Del problemet op i mindre delopgaver.

Erobre : Løs delproblemerne rekursivt.

Forene : Flet eller kombiner løsningerne af underopgaverne for at opnå løsningen på det oprindelige problem.

3. Hvad er nogle eksempler på problemer løst ved hjælp af Divide and Conquer?

Divide and Conquer Algorithm bruges til at sortere algoritmer som Merge Sort og Quick Sort, finde det nærmeste par af punkter, Strassen's Algorithm osv.

4. Hvordan bruger Merge Sort metoden Divide and Conquer?

Merge Sort opdeler arrayet i to halvdele, sorterer rekursivt hver halvdel og flettes derefter de sorterede halvdele for at producere den endelige sorterede array.

5. Hvad er tidskompleksiteten af ​​Divide and Conquer-algoritmer?

Tidskompleksiteten varierer afhængigt af det specifikke problem 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 paralleliseres?

Ja, Divide and Conquer-algoritmer er ofte naturligt paralleliserbare, fordi uafhængige underproblemer kan løses samtidigt. Dette gør dem velegnede til parallelle computermiljøer.

7. Hvad er nogle strategier til at vælge basissagen i Divide and Conquer-algoritmer?

Grundsagen skal være enkel nok til at løse direkte uden yderligere opdeling. Det er ofte valgt ud fra den mindste inputstørrelse, hvor problemet kan løses trivielt.

8. Er der nogen ulemper eller begrænsninger ved at bruge Divide and Conquer?

Selvom Divide and Conquer kan føre til effektive løsninger på mange problemer, er det måske ikke egnet til alle problemtyper. Overhead fra rekursion og kombination af løsninger kan også være et problem for meget store problemstørrelser.

9. Hvordan analyserer du rumkompleksiteten af ​​Divide and Conquer-algoritmer?

Rumkompleksiteten afhænger af faktorer som rekursionsdybden og den ekstra plads, der kræves til at kombinere løsninger. Analyse af rumkompleksitet involverer typisk at overveje den plads, der bruges af hvert rekursivt opkald.

hvad er s i python

10. Hvad er nogle almindelige fordele ved Divide and Conquer Algorithm?

Divide and Conquer-algoritmen har adskillige fordele. Nogle af dem omfatter:

• Løsning af svære problemer
• Algoritme effektivitet
• Parallelisme
• Hukommelsesadgang

Divide and Conquer er en populær algoritmisk teknik inden for datalogi, der går ud på at nedbryde et problem i mindre delproblemer, løse hvert delproblem uafhængigt og derefter kombinere løsningerne på delproblemerne for at løse det oprindelige problem. Grundtanken bag denne teknik er at opdele et problem i mindre, mere overskuelige delproblemer, der lettere kan løses.