I den här självstudien lär du dig hur algoritmen för delning och erövring fungerar. Vi kommer också att jämföra delnings- och erövringsmetoden mot andra metoder för att lösa ett rekursivt problem.
En splittrings- och erövringsalgoritm är en strategi för att lösa ett stort problem genom
- bryta upp problemet i mindre delproblem
- lösa delproblemen och
- genom att kombinera dem för att få önskad effekt.
För att använda delnings- och erövringsalgoritmen används rekursion . Lär dig om rekursion på olika programmeringsspråk:
- Rekursion i Java
- Rekursion i Python
- Rekursion i C ++
Hur delar och erövra algoritmer fungerar?
Här är stegen:
- Dela : Dela det givna problemet i delproblem med rekursion.
- Conquer : Lös de mindre delproblemen rekursivt. Om delproblemet är tillräckligt litet löser du det direkt.
- Kombinera: Kombinera lösningarna på delproblemen som ingår i den rekursiva processen för att lösa det faktiska problemet.
Låt oss förstå detta koncept med hjälp av ett exempel.
Här kommer vi att sortera en matris med delnings- och erövringsmetoden (dvs. slå samman sortering).
- Låt den givna matrisen vara:
Array for merge sort - Dela upp matrisen i två halvor.
Dela upp matrisen i två underdelar
Återigen, dela varje deldel rekursivt i två halvor tills du får enskilda element.
Dela upp matrisen i mindre delar - Kombinera nu de enskilda elementen på ett sorterat sätt. Här, erövra och kombinera steg gå sida vid sida.
Kombinera delarna
Tidskomplexitet
Komplexiteten hos delnings- och erövringsalgoritmen beräknas med hjälp av masterteorem.
T (n) = aT (n / b) + f (n), där, n = storleken på ingången a = antalet delproblem i rekursionen n / b = storleken på varje delproblem. Alla delproblem antas ha samma storlek. f (n) = kostnaden för det arbete som utförts utanför det rekursiva samtalet, vilket inkluderar kostnaden för att dela upp problemet och kostnaden för att slå samman lösningarna
Låt oss ta ett exempel för att hitta tidskomplexiteten hos ett rekursivt problem.
För en sammanslagningssortering kan ekvationen skrivas som:
T (n) = aT (n / b) + f (n) = 2T (n / 2) + O (n) Där a = 2 (varje gång delas ett problem upp i 2 delproblem) n / b = n / 2 (storleken på varje delproblem är hälften av ingången) f (n) = det tar tid att dela upp problemet och slå samman delproblemen T (n / 2) = O (n log n) (För att förstå detta, se masterteorem.) Nu, T (n) = 2T (n log n) + O (n) ≈ O (n log n)
Divide and Conquer Vs Dynamic approach
Delnings- och erövringsstrategin delar upp ett problem i mindre delproblem; dessa delproblem löses ytterligare rekursivt. Resultatet av varje delproblem lagras inte för framtida referens, medan i ett dynamiskt tillvägagångssätt lagras resultatet av varje delproblem för framtida referens.
Använd delnings- och erövringsmetoden när samma delproblem inte löses flera gånger. Använd den dynamiska metoden när resultatet av ett delproblem ska användas flera gånger i framtiden.
Låt oss förstå detta med ett exempel. Anta att vi försöker hitta Fibonacci-serien. Sedan,
Dela och erövra tillvägagångssätt:
fib (n) Om n <2, returnera 1 Annars, returnera f (n - 1) + f (n -2)
Dynamisk strategi:
mem = () fib (n) Om n i mem: returnera mem (n) annat, Om n <2, f = 1 annat, f = f (n - 1) + f (n -2) mem (n) = f tillbaka f
I ett dynamiskt tillvägagångssätt lagrar mem resultatet av varje delproblem.
Fördelar med Divide and Conquer Algorithm
- Komplexiteten för multiplicering av två matriser med den naiva metoden är O (n 3 ), medan användning av delnings- och erövringsmetoden (dvs. Strassens matrixmultiplikation) är O (n 2.8074 ). Detta tillvägagångssätt förenklar också andra problem, såsom Tower of Hanoi.
- Detta tillvägagångssätt är lämpligt för flerbearbetningssystem.
- Det utnyttjar minnescacher effektivt.
Dela och erövra applikationer
- Binär sökning
- Slå ihop sortering
- Snabb sortering
- Strassens matrixmultiplikation
- Karatsuba algoritm
