Söndra och erövra Algoritm är en problemlösningsteknik som används för att lösa problem genom att dela upp huvudproblemet i delproblem, lösa dem individuellt och sedan slå samman dem för att hitta lösningen på det ursprungliga problemet. I den här artikeln kommer vi att diskutera hur Divide and Conquer Algorithm är till hjälp och hur vi kan använda den för att lösa problem.

Innehållsförteckning

• Definition av Divide and Conquer-algoritm
• Arbeta med dela och erövra algoritmen
• Egenskaper för Divide and Conquer-algoritmen
• Exempel på Divide and Conquer-algoritm
• Komplexitetsanalys av Divide and Conquer-algoritmen
• Tillämpningar av Divide and Conquer-algoritmen
• Fördelar med Divide and Conquer-algoritmen
• Nackdelar med Divide and Conquer-algoritmen

Söndra och erövra Algoritmdefinition:

Dela och erövra algoritm innebär att dela upp ett större problem i mindre delproblem, lösa dem självständigt och sedan kombinera deras lösningar för att lösa det ursprungliga problemet. Grundtanken är att rekursivt dela upp problemet i mindre delproblem tills de blir enkla nog att lösas direkt. När väl lösningarna på delproblemen har erhållits, kombineras de sedan för att producera den övergripande lösningen.

Arbeta med dela och erövra algoritmen:

Divide and Conquer-algoritmen kan delas in i tre steg: Dela upp , Erövra och Sammanfoga .

1. Dela:

• Dela upp det ursprungliga problemet i mindre delproblem.
• Varje delproblem bör representera en del av det övergripande problemet.
• Målet är att dela upp problemet tills ingen ytterligare uppdelning är möjlig.

2. Erövra:

• Lös vart och ett av de mindre delproblemen individuellt.
• Om ett delproblem är tillräckligt litet (ofta kallat basfallet) löser vi det direkt utan ytterligare rekursioner.
• Målet är att självständigt hitta lösningar på dessa delproblem.

3. Sammanfoga:

• Kombinera delproblemen för att få den slutliga lösningen på hela problemet.
• När de mindre delproblemen är lösta kombinerar vi rekursivt deras lösningar för att få lösningen på större problem.
• Målet är att formulera en lösning för det ursprungliga problemet genom att slå samman resultaten från delproblemen.

Egenskaper för Divide and Conquer-algoritmen:

Divide and Conquer Algorithm innebär att bryta ner ett problem i mindre, mer hanterbara delar, lösa varje del individuellt och sedan kombinera lösningarna för att lösa det ursprungliga problemet. Egenskaperna för Divide and Conquer-algoritmen är:

• Dela upp problemet : Det första steget är att dela upp problemet i mindre, mer hanterbara delproblem. Denna uppdelning kan göras rekursivt tills delproblemen blir enkla nog att lösa direkt.
• Oberoende av delproblem : Varje delproblem bör vara oberoende av de andra, vilket innebär att lösningen av ett delproblem inte beror på lösningen av ett annat. Detta möjliggör parallell bearbetning eller samtidig exekvering av delproblem, vilket kan leda till effektivitetsvinster.
• Att erövra varje delproblem : När de är uppdelade löses delproblemen individuellt. Detta kan innebära att man tillämpar samma uppdelning och erövra tillvägagångssätt rekursivt tills delproblemen blir enkla nog att lösa direkt, eller så kan det innebära att man tillämpar en annan algoritm eller teknik.
• Kombinera lösningar : Efter att ha löst delproblemen kombineras deras lösningar för att få lösningen på det ursprungliga problemet. Detta kombinationssteg bör vara relativt effektivt och okomplicerat, eftersom lösningarna på delproblemen bör utformas för att passa ihop sömlöst.

Exempel på Divide and Conquer-algoritm:

1. Hitta det maximala elementet i arrayen:

Vi kan använda Divide and Conquer-algoritmen för att hitta det maximala elementet i arrayen genom att dela arrayen i två lika stora underarrayer, hitta maximum av dessa två individuella halvor genom att återigen dela upp dem i två mindre halvor. Detta görs tills vi når subarrays av storlek 1. Efter att ha nått elementen returnerar vi det maximala elementet och kombinerar subarrayerna genom att returnera det maximala i varje subarray.

solig deol

// 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) returnera INT_MIN;  // Om subarrayen bara har ett element, returnera // element if (lo == hi) return a[lo];  int mid = (lo + hej) / 2;  // Få det maximala elementet från den vänstra halvan int leftMax = findMax(a, lo, mid);  // Få det maximala elementet från den högra halvan int rightMax = findMax(a, mid + 1, hi);  // Returnera det maximala elementet från vänster och höger // 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) returnera heltal.MIN_VALUE;  // Om subarrayen bara har ett element, returnera // element if (lo == hi) return a[lo];  int mid = (lo + hej) / 2;  // Få det maximala elementet från den vänstra halvan int leftMax = findMax(a, lo, mid);  // Få det maximala elementet från den högra halvan int rightMax = findMax(a, mid + 1, hi);  // Returnera det maximala elementet från vänster och // höger 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') # Om subarrayen bara har ett element, returnera # elementet om lo == hi: return a[lo] mid = (lo + hi) // 2 # Få det maximala element från den vänstra halvan left_max = find_max(a, lo, mid) # Få maxelementet från den högra halvan right_max = find_max(a, mid + 1, hi) # Returnera det maximala elementet från vänster och höger # halva retur max (vänster_max, höger_max)>

// 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) returnera int.MinValue;  // Om subarrayen bara har ett element, returnera // element if (lo == hi) return a[lo];  int mid = (lo + hej) / 2;  // Få det maximala elementet från den vänstra halvan int leftMax = FindMax(a, lo, mid);  // Få det maximala elementet från den högra halvan int rightMax = FindMax(a, mid + 1, hi);  // Returnera det maximala elementet från vänster och // höger halv retur 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) returnera Number.MIN_VALUE;  // Om subarrayen bara har ett element, returnera // element if (lo === hi) return a[lo];  const mid = Math.floor((lo + hi) / 2);  // Få det maximala elementet från den vänstra halvan const leftMax = findMax(a, lo, mid);  // Få det maximala elementet från den högra halvan const rightMax = findMax(a, mid + 1, hi);  // Returnera det maximala elementet från vänster och höger // half return Math.max(leftMax, rightMax); }>

2. Hitta minimielementet i arrayen:

På liknande sätt kan vi använda Divide and Conquer Algorithm för att hitta minimielementet i arrayen genom att dela arrayen i två lika stora underarrayer, hitta minimum av dessa två individuella halvor genom att återigen dela upp dem i två mindre halvor. Detta görs tills vi når subarrays av storlek 1. Efter att ha nått elementen returnerar vi minimumelementet och kombinerar subarrays genom att returnera minimum i varje subarray.

3. Slå samman sortering:

Vi kan använda Divide and Conquer Algorithm för att sortera arrayen i stigande eller fallande ordning genom att dela arrayen i mindre underarrayer, sortera de mindre underarrayerna och sedan slå samman de sorterade arrayerna för att sortera den ursprungliga arrayen.

Komplexitetsanalys av dela och erövra algoritm:

T(n) = aT(n/b) + f(n), där n = storleken på input a = antalet delproblem i rekursionen n/b = storleken på varje delproblem. Alla delproblem antas ha samma storlek. f(n) = kostnaden för arbetet utanför det rekursiva samtalet, vilket inkluderar kostnaden för att dela upp problemet och kostnaden för att slå samman lösningarna

Tillämpningar av Divide and Conquer-algoritmen:

Följande är några standardalgoritmer som följer Divide and Conquer-algoritmen:

• Quicksort är en sorteringsalgoritm som väljer ett pivotelement och omarrangerar arrayelementen så att alla element mindre än det plockade pivotelementet flyttas till vänster sida av pivoten, och alla större element flyttas till höger sida. Slutligen sorterar algoritmen rekursivt subarrayerna till vänster och höger om pivotelementet.
• Sammanfoga sortering är också en sorteringsalgoritm. Algoritmen delar upp arrayen i två halvor, sorterar dem rekursivt och slår slutligen samman de två sorterade halvorna.
• Närmaste poängpar Problemet är att hitta det närmaste paret av punkter i en uppsättning punkter i x-y-planet. Problemet kan lösas i O(n^2) tid genom att beräkna avstånden för varje par av punkter och jämföra avstånden för att hitta minimum. Divide and Conquer-algoritmen löser problemet i O(N log N) tid.
• Strassens algoritm är en effektiv algoritm för att multiplicera två matriser. En enkel metod för att multiplicera två matriser behöver 3 kapslade loopar och är O(n^3). Strassens algoritm multiplicerar två matriser i O(n^2,8974) tid.
• Cooley–Tukey Fast Fourier Transform (FFT) algoritm är den vanligaste algoritmen för FFT. Det är en dela och erövra algoritm som fungerar i O(N log N) tid.
• Karatsuba-algoritm för snabb multiplikation gör multiplikationen av två binära strängar i O(n^1,59) där n är längden på binär sträng.

Fördelar med Divide and Conquer-algoritmen:

• Att lösa svåra problem: Dela och härska tekniken är ett verktyg för att lösa svåra problem konceptuellt. t.ex. Tower of Hanoi pussel. Det kräver ett sätt att dela upp problemet i delproblem, och lösa dem alla som ett individuellt fall och sedan kombinera delproblem med det ursprungliga problemet.
• Algoritmeffektivitet: Dela-och-härska-algoritmen hjälper ofta till att upptäcka effektiva algoritmer. Det är nyckeln till algoritmer som Quick Sorter och Merge Sort, och snabba Fourier-transformationer.
• Parallellism: Normalt används Divide and Conquer-algoritmer i flerprocessormaskiner som har delat minnessystem där kommunikationen av data mellan processorer inte behöver planeras i förväg, eftersom distinkta delproblem kan exekveras på olika processorer.
• Minnesåtkomst: Dessa algoritmer gör naturligtvis en effektiv användning av minnescacher. Eftersom underproblemen är små nog att lösas i cache utan att använda huvudminnet som är långsammare. Alla algoritmer som använder cache effektivt kallas cache oblivious.

Nackdelar med Divide and Conquer-algoritmen:

• Över huvudet: Processen att dela upp problemet i delproblem och sedan kombinera lösningarna kan kräva ytterligare tid och resurser. Denna omkostnad kan vara betydande för problem som redan är relativt små eller som har en enkel lösning.
• Komplexitet: Att dela upp ett problem i mindre delproblem kan öka komplexiteten i den övergripande lösningen. Detta gäller särskilt när delproblemen är beroende av varandra och måste lösas i en specifik ordning.
• Svårighet att implementera: Vissa problem är svåra att dela upp i mindre delproblem eller kräver en komplex algoritm för att göra det. I dessa fall kan det vara utmanande att implementera en skilda och härska-lösning.
• Minnesbegränsningar: När man arbetar med stora datamängder kan minneskraven för lagring av delproblemens mellanresultat bli en begränsande faktor.

Vanliga frågor (FAQs) om Divide and Conquer-algoritmen:

1. Vad är Divide and Conquer-algoritmen?

Divide and Conquer är en problemlösningsteknik där ett problem delas upp i mindre, mer hanterbara delproblem. Dessa delproblem löses rekursivt och sedan kombineras deras lösningar för att lösa det ursprungliga problemet.

2. Vilka är de viktigaste stegen i Divide and Conquer-algoritmen?

Huvudstegen är:

Dela upp : Dela upp problemet i mindre delproblem.

Erövra : Lös delproblemen rekursivt.

Kombinera : Slå ihop eller kombinera lösningarna för delproblemen för att få lösningen på det ursprungliga problemet.

3. Vilka är några exempel på problem som lösts med Divide and Conquer?

Divide and Conquer Algorithm används för att sortera algoritmer som Merge Sort och Quick Sort, hitta närmaste poängpar, Strassens algoritm, etc.

4. Hur använder Merge Sort metoden Divide and Conquer?

Merge Sortering delar upp arrayen i två halvor, sorterar rekursivt varje halva och slår sedan samman de sorterade halvorna för att producera den slutliga sorterade arrayen.

5. Vad är tidskomplexiteten för Divide and Conquer-algoritmer?

Tidskomplexiteten varierar beroende på det specifika problemet och hur det implementeras. I allmänhet har många Divide and Conquer-algoritmer en tidskomplexitet på O(n log n) eller bättre.

6. Kan Divide and Conquer-algoritmer parallelliseras?

Ja, Divide and Conquer-algoritmer är ofta naturligt parallelliserbara eftersom oberoende delproblem kan lösas samtidigt. Detta gör dem lämpliga för parallella datormiljöer.

7. Vilka är några strategier för att välja basfallet i Divide and Conquer-algoritmer?

Basfallet bör vara enkelt nog att lösa direkt, utan ytterligare uppdelning. Det väljs ofta utifrån den minsta inmatningsstorleken där problemet kan lösas trivialt.

8. Finns det några nackdelar eller begränsningar med att använda Divide and Conquer?

Även om Divide and Conquer kan leda till effektiva lösningar för många problem, är det kanske inte lämpligt för alla problemtyper. Overhead från rekursion och att kombinera lösningar kan också vara ett problem för mycket stora problemstorlekar.

9. Hur analyserar du rymdkomplexiteten hos Divide and Conquer-algoritmer?

Utrymmeskomplexitet beror på faktorer som rekursionsdjupet och det extra utrymmet som krävs för att kombinera lösningar. Att analysera rymdkomplexiteten innebär vanligtvis att man tar hänsyn till det utrymme som används av varje rekursivt anrop.

10. Vilka är några vanliga fördelar med Divide and Conquer Algorithm?

Divide and Conquer-algoritmen har många fördelar. Några av dem inkluderar:

array.från java

• Att lösa svåra problem
• Algoritm effektivitet
• Parallellism
• Minnesåtkomst

Divide and Conquer är en populär algoritmisk teknik inom datavetenskap som går ut på att bryta ner ett problem i mindre delproblem, lösa varje delproblem självständigt och sedan kombinera lösningarna på delproblemen för att lösa det ursprungliga problemet. Grundtanken bakom denna teknik är att dela upp ett problem i mindre, mer hanterbara delproblem som kan lösas lättare.