logo

TechCodeview

Verdeel en heers algoritme

Verdeel en heers-algoritme is een probleemoplossende strategie waarbij een complex probleem wordt opgedeeld in kleinere, beter beheersbare delen, waarbij elk onderdeel afzonderlijk wordt opgelost en vervolgens de oplossingen worden gecombineerd om het oorspronkelijke probleem op te lossen. Het is een veelgebruikte algoritmische techniek in de informatica en wiskunde.

Voorbeeld: In de Sortering samenvoegen algoritme, de Verdeel en heers strategie wordt gebruikt om een ​​lijst met elementen te sorteren. De onderstaande afbeelding illustreert de deel- en samenvoegingsstatussen waarmee de array kan worden gesorteerd Sortering samenvoegen .



Inhoudsopgave

Wat is het verdeel en heers-algoritme?

Verdeel en heers is een probleemoplossende techniek waarbij een groter probleem in deelproblemen wordt opgedeeld, waarbij de deelproblemen onafhankelijk worden opgelost en de oplossingen van die deelproblemen worden gecombineerd om tot de oplossing van het grotere probleem te komen.



Fasen van het verdeel en heers-algoritme:

Het verdeel-en-heers-algoritme kan in drie fasen worden verdeeld: Verdeling , Veroveren En Samenvoegen .

1. Verdeel:

  • Verdeel het oorspronkelijke probleem in kleinere deelproblemen.
  • Elk deelprobleem moet een deel van het totale probleem vertegenwoordigen.
  • Het doel is om het probleem te verdelen totdat er geen verdere verdeling meer mogelijk is.

2. Verover:

  • Los elk van de kleinere deelproblemen afzonderlijk op.
  • Als een deelprobleem klein genoeg is (vaak het basisprobleem genoemd), lossen we het direct op, zonder verdere recursie.
  • Het doel is om voor deze deelproblemen zelfstandig oplossingen te vinden.

3. Samenvoegen:

  • Combineer de deelproblemen om de uiteindelijke oplossing van het hele probleem te krijgen.
  • Zodra de kleinere deelproblemen zijn opgelost, combineren we hun oplossingen recursief om de oplossing van een groter probleem te krijgen.
  • Het doel is om een ​​oplossing voor het oorspronkelijke probleem te formuleren door de resultaten van de deelproblemen samen te voegen.

Toepassingen van het verdeel en heers-algoritme:

  • Sortering samenvoegen: Samenvoegsortering is een klassiek voorbeeld van een verdeel-en-heers-sorteeralgoritme. Het verdeelt de array in kleinere subarrays, sorteert ze afzonderlijk en voegt ze vervolgens samen om de gesorteerde array te verkrijgen.
  • Mediaan vinden: De mediaan van een reeks getallen kan worden gevonden met behulp van een verdeel-en-heers-aanpak. Door de verzameling recursief in kleinere deelverzamelingen te verdelen, kan de mediaan efficiënt worden bepaald.
  • Min- en Max-bevinding: Het Divide and Conquer-algoritme kan worden gebruikt om tegelijkertijd zowel de minimale als de maximale elementen in een array te vinden. Door de array in twee helften te splitsen en de min-max-paren van elke helft te vergelijken, kunnen de totale min en max worden geïdentificeerd in logaritmische tijdscomplexiteit.
  • Matrix vermenigvuldiging: Het algoritme van Strassen voor matrixvermenigvuldiging is een verdeel-en-heerstechniek die het aantal vermenigvuldigingen dat nodig is voor grote matrices vermindert door de matrices op te splitsen in kleinere submatrices en hun producten te combineren.
  • Probleem met het dichtstbijzijnde paar: Het dichtstbijzijnde paarprobleem omvat het vinden van de twee dichtstbijzijnde punten in een reeks punten in een multidimensionale ruimte. Een verdeel-en-heers-algoritme, zoals het verdeel-en-heers-algoritme voor het dichtste paar, kan dit probleem efficiënt oplossen door de punten recursief te verdelen en de oplossingen van de deelproblemen samen te voegen.

Basisprincipes van het verdeel en heers-algoritme:

Standaardalgoritmen ingeschakeld Verdeel en heers algoritme :

Op binaire zoekopdrachten gebaseerde problemen:

  • Zoek een piekelement in een gegeven array
  • Controleer op meerderheidselement in een gesorteerde array
  • K-de element van twee gesorteerde arrays
  • Zoek het aantal nullen
  • Zoek het aantal rotaties in de geroteerde, gesorteerde array
  • Zoek het punt waarop een monotoon stijgende functie de eerste keer positief wordt
  • Mediaan van twee gesorteerde arrays
  • Mediaan van twee gesorteerde matrices van verschillende grootte
  • Het partitieprobleem van de schilder met behulp van binair zoeken

Oefen problemen op Verdeel en heers algoritme :

  • Vierkantswortel van een geheel getal
  • Maximum en minimum van een array met een minimum aantal vergelijkingen
  • Vind de frequentie van elk element in een array met beperkt bereik in minder dan O(n) tijd
  • Tegelprobleem
  • Tel inversies
  • Het skylineprobleem
  • Zoeken in een rij- en kolomsgewijs gesorteerde 2D-array
  • Wijs een minimumaantal pagina's toe
  • Modulaire machtsverheffen (macht in modulaire rekenkunde)

Snelle links:

  • Leer datastructuur en algoritmen | DSA-zelfstudie
  • ‘Oefenproblemen’ over verdeel en heers
  • ‘Quizzen’ over Verdeel en Heers