Divide and Conquer-algoritme er en problemløsningsstrategi, der går ud på at nedbryde et komplekst problem i mindre, mere håndterbare dele, løse hver enkelt del individuelt og derefter kombinere løsningerne for at løse det oprindelige problem. Det er en meget brugt algoritmisk teknik inden for datalogi og matematik.

Eksempel: I den Flet sortering algoritme, den Del og hersk strategi bruges til at sortere en liste over elementer. Nedenstående billede illustrerer opdelings- og flettetilstandene for at sortere arrayet ved hjælp af Flet sortering .

Indholdsfortegnelse

• Hvad er Divide and Conquer?
• Stadier af del og hersk
• Anvendelser af Divide and Conquer
• Grundlæggende om Divide and Conquer
• Standardalgoritmer om Divide and Conquer
• Binær søgning baserede problemer
• Øv problemer på Divide and Conquer

Hvad er Divide and Conquer-algoritmen?

Divide and Conquer er en problemløsningsteknik, der involverer at opdele et større problem i delproblemer, løse delproblemerne uafhængigt og kombinere løsningerne af disse delproblemer for at få løsningen på det større problem.

Stadier af opdeling og hersk-algoritme:

Divide and Conquer-algoritmen kan opdeles i tre faser: 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.

Anvendelser af Divide and Conquer-algoritmen:

• Flet sortering: Merge sort er et klassisk eksempel på en opdel og hersk sorteringsalgoritme. Det opdeler arrayet i mindre underarrays, sorterer dem individuelt og flettes derefter sammen for at opnå det sorterede array.
• Medianfund: Medianen af ​​et sæt tal kan findes ved hjælp af en del og hersk tilgang. Ved rekursivt at opdele sættet i mindre delmængder kan medianen bestemmes effektivt.
• Min og Max fund: Divide and Conquer-algoritmen kan bruges til at finde både minimums- og maksimumselementerne i et array samtidigt. Ved at opdele arrayet i halvdele og sammenligne min-max-parrene fra hver halvdel, kan de overordnede min og max identificeres i logaritmisk tidskompleksitet.
• Matrix multiplikation: Strassens algoritme for matrixmultiplikation er en del og hersk-teknik, der reducerer antallet af multiplikationer, der kræves for store matricer, ved at nedbryde matricerne i mindre submatricer og kombinere deres produkter.
• Problem med det nærmeste par: Det nærmeste par-problem involverer at finde de to nærmeste punkter i et sæt punkter i et flerdimensionelt rum. En divide and conquer algoritme, såsom divide and conquer closest pair algoritmen, kan effektivt løse dette problem ved rekursivt at dividere punkterne og flette løsningerne fra underproblemerne.

Grundlæggende om Divide and Conquer-algoritmen:

• Introduktion til Divide and Conquer
• Dynamisk programmering vs Divide-and-Conquer
• Formindsk og erobre
• Avanceret mastersætning til gentagelser af divider og hersk

Standardalgoritmer er slået til Divide and Conquer-algoritme :

• Binær søgning
• Flet sortering
• Hurtig sortering
• Beregn pow(x, n)
• Karatsuba algoritme til hurtig multiplikation
• Strassens Matrix Multiplikation
• Convex Hull (Simple Divide and Conquer-algoritme)
• Quickhull-algoritme til konveks skrog

Binær søgning baseret problemer:

• Find et topelement i et givet array
• Tjek for Majority Element i et sorteret array
• K-te element af to sorterede arrays
• Find antallet af nuller
• Find rotationstællingen i roteret sorteret array
• Find det punkt, hvor en monotont stigende funktion bliver positiv første gang
• Medianen af ​​to sorterede arrays
• Medianen af ​​to sorterede arrays af forskellig størrelse
• Malerens partitionsproblem ved hjælp af binær søgning

Øv problemer på Divide and Conquer-algoritme :

• Kvadratroden af ​​et heltal
• Maksimum og minimum af et array ved brug af minimum antal sammenligninger
• Find frekvensen af ​​hvert element i et array med begrænset rækkevidde på mindre end O(n) tid
• Problem med flisebelægning
• Tæl inversioner
• Skyline-problemet
• Søg i en række- og kolonnevis sorteret 2D-array
• Tildel minimum antal sider
• Modulær eksponentiering (kraft i modulær aritmetik)

Hurtige links :

• Lær datastruktur og algoritmer | DSA Tutorial
• 'Practice Problemer' om Divide and Conquer
• 'Quizz' om Divide and Conquer