logo

TechCodeview

Divide and Conquer-algoritmen

Divide and Conquer-algoritmen er en problemløsningsstrategi som innebærer å bryte ned et komplekst problem i mindre, mer håndterbare deler, løse hver del individuelt, og deretter kombinere løsningene for å løse det opprinnelige problemet. Det er en mye brukt algoritmisk teknikk innen informatikk og matematikk.

Eksempel: I Slå sammen sortering algoritme, den Splitt og hersk strategi brukes til å sortere en liste over elementer. Bildet nedenfor illustrerer delings- og sammenslåingstilstandene for å sortere matrisen ved hjelp av Slå sammen sortering .



Innholdsfortegnelse

Hva er Divide and Conquer-algoritmen?

Divide and Conquer er en problemløsningsteknikk som innebærer å dele opp et større problem i delproblemer, løse delproblemene uavhengig og kombinere løsningene til disse delproblemene for å få løsningen på det større problemet.



Stadier av Divide and Conquer-algoritmen:

Divide and Conquer-algoritmen kan deles inn i tre stadier: 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.

Anvendelser av Divide and Conquer-algoritmen:

  • Slå sammen sortering: Slå sammen sortering er et klassisk eksempel på en divisjonssortering-algoritme. Den bryter ned matrisen i mindre undermatriser, sorterer dem individuelt og slår dem deretter sammen for å oppnå den sorterte matrisen.
  • Medianfunn: Medianen til et sett med tall kan bli funnet ved å bruke en del og hersk-tilnærming. Ved rekursivt å dele settet i mindre delmengder, kan medianen bestemmes effektivt.
  • Min og maks funn: Divide and Conquer-algoritmen kan brukes til å finne både minimums- og maksimumselementene i en matrise samtidig. Ved å dele opp matrisen i halvdeler og sammenligne min-maks-parene fra hver halvdel, kan den totale min og maks identifiseres i logaritmisk tidskompleksitet.
  • Matrisemultiplikasjon: Strassens algoritme for matrisemultiplikasjon er en del og hersk-teknikk som reduserer antallet multiplikasjoner som kreves for store matriser ved å bryte ned matrisene til mindre submatriser og kombinere produktene deres.
  • Problem med nærmeste par: Det nærmeste parproblemet innebærer å finne de to nærmeste punktene i et sett med punkter i et flerdimensjonalt rom. En dele-og-hersk-algoritme, slik som algoritmen for å dele og hersk nærmeste par, kan effektivt løse dette problemet ved å rekursivt dele punktene og slå sammen løsningene fra delproblemene.

Grunnleggende om Divide and Conquer-algoritmen:

Standard algoritmer på Divide and Conquer-algoritmen :

Binære søk baserte problemer:

  • Finn et toppelement i en gitt matrise
  • Se etter Majority Element i en sortert matrise
  • K-te element av to sorterte matriser
  • Finn antall nuller
  • Finn rotasjonstellingen i rotert sortert matrise
  • Finn punktet hvor en monotont økende funksjon blir positiv første gang
  • Median av to sorterte matriser
  • Median av to sorterte matriser av forskjellige størrelser
  • Malerens partisjonsproblem ved hjelp av binært søk

Øv problemer på Divide and Conquer-algoritmen :

  • Kvadratroten av et heltall
  • Maksimum og minimum av en matrise ved å bruke minimum antall sammenligninger
  • Finn frekvensen til hvert element i et begrenset område på mindre enn O(n) tid
  • Problem med flislegging
  • Tell inversjoner
  • Skyline-problemet
  • Søk i en rad- og kolonnevis sortert 2D-matrise
  • Tildel minimum antall sider
  • Modulær eksponentiering (kraft i modulær aritmetikk)

Hurtigkoblinger :

  • Lær datastruktur og algoritmer | DSA veiledning
  • 'Øv problemer' om Divide and Conquer
  • «Quizzer» om Divide and Conquer