logo

TechCodeview

Dela och erövra algoritm

Dela och erövra algoritm är en problemlösningsstrategi som går ut på att bryta ner ett komplext problem i mindre, mer hanterbara delar, lösa varje del individuellt och sedan kombinera lösningarna för att lösa det ursprungliga problemet. Det är en allmänt använd algoritmisk teknik inom datavetenskap och matematik.

Exempel: I den Sammanfoga sortering algoritm, den Söndra och erövra strategi används för att sortera en lista med element. Bilden nedan illustrerar delnings- och sammanslagningstillstånden för att sortera arrayen med hjälp av Sammanfoga sortering .



Innehållsförteckning

Vad är Divide and Conquer-algoritmen?

Divide and Conquer är en problemlösningsteknik som går ut på att dela upp ett större problem i delproblem, lösa delproblemen självständigt och kombinera lösningarna för dessa delproblem för att få lösningen på det större problemet.



Stadier av dela och erövra algoritm:

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.

Tillämpningar av Divide and Conquer-algoritmen:

  • Slå samman sortering: Slå samman sortering är ett klassiskt exempel på en sorteringsalgoritm för dividera och erövra. Den delar upp arrayen i mindre underarrayer, sorterar dem individuellt och slår sedan samman dem för att erhålla den sorterade arrayen.
  • Medianfynd: Medianen för en uppsättning siffror kan hittas med hjälp av ett dividera och erövra tillvägagångssätt. Genom att rekursivt dela upp mängden i mindre delmängder kan medianen bestämmas effektivt.
  • Min och Max fynd: Divide and Conquer-algoritmen kan användas för att hitta både minimum- och maximumelementen i en array samtidigt. Genom att dela upp arrayen i halvor och jämföra min-max-paren från varje halva, kan den totala min och max identifieras i logaritmisk tidskomplexitet.
  • Matrismultiplikation: Strassens algoritm för matrismultiplikation är en dela och erövra-teknik som minskar antalet multiplikationer som krävs för stora matriser genom att bryta ner matriserna i mindre submatriser och kombinera deras produkter.
  • Närmaste parproblem: Det närmaste parproblemet innebär att hitta de två närmaste punkterna i en uppsättning punkter i ett flerdimensionellt utrymme. En dela och erövra-algoritm, som algoritmen dividera och erövra närmaste par, kan effektivt lösa detta problem genom att rekursivt dividera punkterna och slå samman lösningarna från delproblemen.

Grunderna i Divide and Conquer-algoritmen:

Standardalgoritmer på Dela och erövra algoritm :

Binära sökningsbaserade problem:

  • Hitta ett toppelement i en given array
  • Kontrollera efter majoritetselement i en sorterad array
  • K-te element av två sorterade arrayer
  • Hitta antalet nollor
  • Hitta rotationsräkningen i roterad sorterad matris
  • Hitta punkten där en monotont ökande funktion blir positiv första gången
  • Median för två sorterade arrayer
  • Median av två sorterade arrayer av olika storlekar
  • Målarens partitionsproblem med binär sökning

Öva problem på Dela och erövra algoritm :

  • Kvadratroten ur ett heltal
  • Maximalt och minimum av en array med minsta antal jämförelser
  • Hitta frekvensen för varje element i ett begränsat intervall på mindre än O(n) tid
  • Kakelproblem
  • Räkna inversioner
  • Skylineproblemet
  • Sök i en radvis och kolumnvis sorterad 2D-matris
  • Tilldela minsta antal sidor
  • Modulär exponentiering (kraft i modulär aritmetik)

Snabblänkar :

  • Lär dig datastruktur och algoritmer | Handledning för DSA
  • 'Träna problem' om Divide and Conquer
  • 'Frågesporter' om Divide and Conquer