In deze tutorial leer je hoe het verdeel en heers-algoritme werkt. We zullen ook de verdeel en heersbenadering vergelijken met andere benaderingen om een recursief probleem op te lossen.
Een verdeel en heers-algoritme is een strategie om een groot probleem op te lossen door
- het probleem opdelen in kleinere deelproblemen
- het oplossen van de deelproblemen, en
- ze combineren om de gewenste output te krijgen.
Om het verdeel en heers-algoritme te gebruiken, wordt recursie gebruikt. Leer meer over recursie in verschillende programmeertalen:
- Recursie in Java
- Recursie in Python
- Recursie in C ++
Hoe verdeel en heers algoritmen werken?
Hier zijn de betrokken stappen:
- Verdelen : Verdeel het gegeven probleem in deelproblemen door middel van recursie.
- Veroveren : Los de kleinere deelproblemen recursief op. Als het subprobleem klein genoeg is, los het dan direct op.
- Combineren: Combineer de oplossingen van de deelproblemen die deel uitmaken van het recursieve proces om het eigenlijke probleem op te lossen.
Laten we dit concept begrijpen met behulp van een voorbeeld.
Hier zullen we een array sorteren met behulp van de verdeel en heersbenadering (dwz samenvoegen sorteren).
- Laat de gegeven array zijn:
Array voor samenvoegsortering - Verdeel de array in twee helften.
Verdeel de array in twee subparts
Nogmaals, verdeel elk subpart recursief in twee helften totdat je individuele elementen krijgt.
Verdeel de array in kleinere subdelen - Combineer nu de afzonderlijke elementen op een gesorteerde manier. Hier gaan overwinnings- en combinatietrappen naast elkaar.
Combineer de subonderdelen
Tijdscomplexiteit
De complexiteit van het verdeel en heers-algoritme wordt berekend met behulp van de hoofdstelling.
T (n) = aT (n / b) + f (n), waarbij, n = grootte van invoer a = aantal subproblemen in de recursie n / b = grootte van elk subprobleem. Aangenomen wordt dat alle subproblemen dezelfde omvang hebben. f (n) = kosten van het werk dat is gedaan buiten de recursieve oproep, inclusief de kosten voor het verdelen van het probleem en de kosten voor het samenvoegen van de oplossingen
Laten we een voorbeeld nemen om de tijdcomplexiteit van een recursief probleem te vinden.
Voor een samenvoegsortering kan de vergelijking worden geschreven als:
T (n) = aT (n / b) + f (n) = 2T (n / 2) + O (n) Waarbij, a = 2 (telkens wordt een probleem opgedeeld in 2 deelproblemen) n / b = n / 2 (grootte van elk subprobleem is de helft van de invoer) f (n) = tijd die nodig is om het probleem te verdelen en de subproblemen samen te voegen T (n / 2) = O (n log n) (Om dit te begrijpen, raadpleeg de hoofdstelling.) Nu, T (n) = 2T (n log n) + O (n) ≈ O (n log n)
Verdeel en heers versus dynamische benadering
De verdeel en heersbenadering verdeelt een probleem in kleinere deelproblemen; deze deelproblemen worden recursief verder opgelost. Het resultaat van elk subprobleem wordt niet opgeslagen voor toekomstige referentie, terwijl bij een dynamische benadering het resultaat van elk subprobleem wordt opgeslagen voor toekomstige referentie.
Gebruik de verdeel en heersbenadering wanneer hetzelfde subprobleem niet meerdere keren wordt opgelost. Gebruik de dynamische benadering wanneer het resultaat van een deelprobleem in de toekomst meerdere keren moet worden gebruikt.
Laten we dit begrijpen met een voorbeeld. Stel dat we de Fibonacci-reeks proberen te vinden. Vervolgens,
Verdeel en heers aanpak:
fib (n) Als n <2, retourneer 1 Else, retourneer f (n - 1) + f (n -2)
Dynamische aanpak:
mem = () fib (n) If n in mem: retourneer mem (n) else, If n <2, f = 1 else, f = f (n - 1) + f (n -2) mem (n) = f terug f
Bij een dynamische benadering slaat mem het resultaat van elk deelprobleem op.
Voordelen van het verdeel en heers-algoritme
- De complexiteit voor de vermenigvuldiging van twee matrices met behulp van de naïeve methode is O (n 3 ), terwijl het gebruik van de verdeel en heers-benadering (dwz Strassen's matrixvermenigvuldiging) O (n 2.8074 ) is. Deze benadering vereenvoudigt ook andere problemen, zoals de Toren van Hanoi.
- Deze benadering is geschikt voor systemen met meerdere verwerkingen.
- Het maakt efficiënt gebruik van geheugencaches.
Verdeel en heers applicaties
- Binaire zoekopdracht
- Samenvoegen Sorteren
- Snel sorteren
- Strassen's Matrixvermenigvuldiging
- Karatsuba-algoritme
