logo

TechCodeview

Algoritmus rozdeľuj a panuj

Algoritmus rozdeľuj a panuj je stratégia riešenia problémov, ktorá zahŕňa rozloženie zložitého problému na menšie, lepšie zvládnuteľné časti, riešenie každej časti jednotlivo a následné skombinovanie riešení na vyriešenie pôvodného problému. Je to široko používaná algoritmická technika v informatike a matematike.

Príklad: V Zlúčiť triedenie algoritmus, Rozdeľuj a panuj stratégia sa používa na triedenie zoznamu prvkov. Nižšie uvedený obrázok ilustruje stavy rozdelenia a zlúčenia na triedenie poľa Zlúčiť triedenie .



Obsah

Čo je to algoritmus rozdeľuj a panuj?

Rozdeľuj a panuj je technika riešenia problémov, ktorá zahŕňa rozdelenie väčšieho problému na čiastkové problémy, samostatné riešenie čiastkových problémov a kombinovanie riešení týchto čiastkových problémov s cieľom získať riešenie väčšieho problému.



Etapy algoritmu rozdelenia a panovania:

Algoritmus rozdeľovania a panovania možno rozdeliť do troch etáp: Rozdeliť , dobyť a Zlúčiť .

1. Rozdeliť:

  • Rozdeľte pôvodný problém na menšie čiastkové problémy.
  • Každý podproblém by mal predstavovať časť celkového problému.
  • Cieľom je rozdeliť problém dovtedy, kým ďalšie rozdelenie nebude možné.

2. Dobyť:

  • Vyriešte každý z menších podproblémov jednotlivo.
  • Ak je podproblém dostatočne malý (často označovaný ako základný prípad), riešime ho priamo bez ďalšej rekurzie.
  • Cieľom je nájsť riešenia pre tieto podproblémy nezávisle.

3. Zlúčiť:

  • Spojením čiastkových problémov získate konečné riešenie celého problému.
  • Keď sú menšie podproblémy vyriešené, rekurzívne kombinujeme ich riešenia, aby sme dostali riešenie väčšieho problému.
  • Cieľom je sformulovať riešenie pôvodného problému zlúčením výsledkov z podproblémov.

Aplikácie algoritmu rozdeľuj a panuj:

  • Zlúčiť triedenie: Zlúčiť triedenie je klasickým príkladom triediaceho algoritmu rozdeľuj a panuj. Rozdelí pole na menšie podpolia, zoradí ich jednotlivo a potom ich zlúči, aby sa získalo zoradené pole.
  • Medián nálezu: Medián množiny čísel možno nájsť pomocou prístupu rozdeľuj a panuj. Rekurzívnym rozdelením súboru na menšie podmnožiny možno efektívne určiť medián.
  • Zistenie min a max: Algoritmus Divide and Conquer možno použiť na súčasné nájdenie minimálnych aj maximálnych prvkov v poli. Rozdelením poľa na polovice a porovnaním párov min-max z každej polovice možno identifikovať celkové minimum a maximum v logaritmickej časovej zložitosti.
  • Násobenie matice: Strassenov algoritmus na násobenie matíc je technika rozdeľovania a panovania, ktorá znižuje počet násobení potrebných pre veľké matice rozdelením matíc na menšie podmatice a kombináciou ich produktov.
  • Problém s najbližším párom: Problém najbližšieho páru zahŕňa nájdenie dvoch najbližších bodov v množine bodov vo viacrozmernom priestore. Algoritmus rozdelenia a panovania, ako je napríklad algoritmus najbližšieho páru rozdeľuj a panuj, môže tento problém efektívne vyriešiť rekurzívnym delením bodov a spájaním riešení z podproblémov.

Základy algoritmu rozdeľuj a panuj:

Štandardné algoritmy zapnuté Algoritmus rozdeľuj a panuj :

Problémy založené na binárnom vyhľadávaní:

  • Nájdite vrcholový prvok v danom poli
  • Skontrolujte väčšinový prvok v zoradenom poli
  • K-tý prvok dvoch triedených polí
  • Nájdite počet núl
  • Nájdite počet rotácií v poli Rotated Sorted
  • Nájdite bod, v ktorom sa monotónne rastúca funkcia stane kladnou prvýkrát
  • Medián dvoch triedených polí
  • Medián dvoch triedených polí rôznych veľkostí
  • Problém s partíciou maliara pomocou binárneho vyhľadávania

Cvičte problémy na Algoritmus rozdeľuj a panuj :

  • Druhá odmocnina z celého čísla
  • Maximum a minimum poľa pomocou minimálneho počtu porovnaní
  • Nájdite frekvenciu každého prvku v poli s obmedzeným rozsahom za menej ako O(n) čas
  • Problém s obkladmi
  • Počítajte inverzie
  • Problém panorámy
  • Hľadajte v 2D poli zoradenom po riadkoch a stĺpcoch
  • Prideľte minimálny počet strán
  • Modulárne umocňovanie (výkon v modulárnej aritmetike)

Rýchle odkazy:

  • Naučte sa dátovú štruktúru a algoritmy | Príručka DSA
  • „Problémy s precvičovaním“ Rozdeľuj a panuj
  • „Kvízy“ na tému Rozdeľ a panuj