I denne vejledning lærer du, hvordan opdelings- og erobringsalgoritmen fungerer. Vi sammenligner også opdelings- og erobringsmetoden med andre tilgange til løsning af et rekursivt problem.
En opdeling og erobringsalgoritme er en strategi til løsning af et stort problem
- opdele problemet i mindre delproblemer
- løsning af underproblemer, og
- ved at kombinere dem for at få det ønskede output.
For at bruge opdelings- og erobringsalgoritmen bruges rekursion . Lær om rekursion på forskellige programmeringssprog:
- Rekursion i Java
- Rekursion i Python
- Rekursion i C ++
Hvordan opdele og erobre algoritmer fungerer?
Her er de involverede trin:
- Opdel : Opdel det givne problem i delproblemer ved hjælp af rekursion.
- Conquer : Løs de mindre delproblemer rekursivt. Hvis underproblemet er lille nok, skal du løse det direkte.
- Kombiner: Kombiner løsningerne på de delproblemer, der er en del af den rekursive proces, for at løse det aktuelle problem.
Lad os forstå dette koncept ved hjælp af et eksempel.
Her vil vi sortere et array ved hjælp af divide and conquer tilgangen (dvs. flette sortering).
- Lad det givne array være:
Array for merge sort - Del arrayet i to halvdele.
Opdel arrayet i to subparts
Igen opdeler hver subpart rekursivt i to halvdele, indtil du får individuelle elementer.
Opdel arrayet i mindre underdele - Nu skal du kombinere de enkelte elementer sorteret. Her erobre og kombinere trin gå side om side.
Kombiner delene
Tidskompleksitet
Kompleksiteten af opdelings- og erobringsalgoritmen beregnes ved hjælp af master sætningen.
T (n) = aT (n / b) + f (n), hvor, n = størrelse på input a = antal delproblemer i rekursion n / b = størrelse på hvert delproblem. Alle delproblemer antages at have samme størrelse. f (n) = omkostningerne ved det arbejde, der er udført uden for det rekursive opkald, som inkluderer omkostningerne ved at opdele problemet og omkostningerne ved at slå sammen løsninger
Lad os tage et eksempel for at finde tidskompleksiteten af et rekursivt problem.
For en fusionssortering kan ligningen skrives som:
T (n) = aT (n / b) + f (n) = 2T (n / 2) + O (n) Hvor, a = 2 (hver gang et problem er opdelt i 2 delproblemer) n / b = n / 2 (størrelsen på hvert underproblem er halvdelen af input) f (n) = det tager tid at opdele problemet og flette delproblemerne T (n / 2) = O (n log n) (For at forstå dette henvises til master sætningen.) Nu, T (n) = 2T (n log n) + O (n) ≈ O (n log n)
Divide and Conquer Vs Dynamic tilgang
Opdelings- og erobringsmetoden opdeler et problem i mindre delproblemer; disse underproblemer løses yderligere rekursivt. Resultatet af hvert delproblem lagres ikke til fremtidig reference, mens resultatet af hvert delproblem i en dynamisk tilgang lagres til fremtidig reference.
Brug divide and conquer tilgangen, når det samme underproblem ikke løses flere gange. Brug den dynamiske tilgang, når resultatet af et underproblem skal bruges flere gange i fremtiden.
Lad os forstå dette med et eksempel. Antag, at vi prøver at finde Fibonacci-serien. Derefter,
Opdel og sejr tilgang:
fib (n) Hvis n <2, returner 1 Ellers, returner f (n - 1) + f (n -2)
Dynamisk tilgang:
mem = () fib (n) Hvis n i mem: returner mem (n) andet, Hvis n <2, f = 1 andet, f = f (n - 1) + f (n -2) mem (n) = f returnere f
I en dynamisk tilgang gemmer mem resultatet af hvert underproblem.
Fordele ved Opdel og erobre algoritme
- Kompleksiteten for multiplikation af to matricer ved hjælp af den naive metode er O (n 3 ), mens anvendelse af delings- og erobringsmetoden (dvs. Strassens matrixmultiplikation) er O (n 2.8074 ). Denne tilgang forenkler også andre problemer, såsom Tower of Hanoi.
- Denne tilgang er velegnet til multiprocessing-systemer.
- Det gør effektiv brug af hukommelsescacher.
Opdel og erobre applikationer
- Binær søgning
- Flet sortering
- Hurtig sortering
- Strassens matrixmultiplikation
- Karatsuba Algoritme
