logo

TechCodeview

Algoritem deli in vladaj

Algoritem deli in vladaj je strategija reševanja problemov, ki vključuje razčlenitev kompleksnega problema na manjše, bolj obvladljive dele, reševanje vsakega dela posebej in nato združevanje rešitev za rešitev prvotnega problema. Je široko uporabljena algoritemska tehnika v računalništvu in matematiki.

primer: V Spoji Razvrsti algoritem, Razdeli in vladaj strategija se uporablja za razvrščanje seznama elementov. Spodnja slika ponazarja stanja delitve in združevanja za razvrščanje matrike Spoji Razvrsti .



predmet matrike v Javi

Kazalo

Kaj je algoritem razdeli in vladaj?

Deli in vladaj je tehnika reševanja problemov, ki vključuje razdelitev večjega problema na podprobleme, neodvisno reševanje podproblemov in združevanje rešitev teh podproblemov, da bi dobili rešitev večjega problema.



char v celo število java

Faze algoritma deli in vladaj:

Algoritem razdeli in vladaj lahko razdelimo na tri stopnje: Razdeli , osvojiti in Spoji .

1. Razdelite:

  • Prvotni problem razdelite na manjše podprobleme.
  • Vsak podproblem naj predstavlja del celotnega problema.
  • Cilj je razdeliti problem, dokler nadaljnja delitev ni več mogoča.

2. Osvoji:

  • Rešite vsakega od manjših podproblemov posebej.
  • Če je podproblem dovolj majhen (pogosto imenovan osnovni primer), ga rešimo neposredno brez nadaljnje rekurzije.
  • Cilj je samostojno najti rešitve za te podprobleme.

3. Združi:

  • Združite podprobleme, da dobite končno rešitev celotnega problema.
  • Ko so manjši podproblemi rešeni, njihove rešitve rekurzivno združimo, da dobimo rešitev večjega problema.
  • Cilj je oblikovati rešitev za prvotni problem z združitvijo rezultatov iz podproblemov.

Uporaba algoritma deli in vladaj:

  • Spoji Razvrsti: Razvrščanje z združitvijo je klasičen primer algoritma za razvrščanje po principu »deli in vladaj«. Matriko razdeli na manjše podmatrike, jih razvrsti posamično in nato združi, da dobi razvrščeno matriko.
  • Srednja ugotovitev: Mediano niza števil je mogoče najti s pristopom deli in vladaj. Z rekurzivno delitvijo množice na manjše podmnožice je mogoče učinkovito določiti mediano.
  • Najmanjša in največja ugotovitev: Algoritem razdeli in vladaj lahko uporabite za iskanje najmanjših in največjih elementov v matriki hkrati. Z razdelitvijo matrike na polovice in primerjavo parov min-max iz vsake polovice je mogoče identificirati skupni min in max v logaritemski časovni kompleksnosti.
  • Matrično množenje: Strassenov algoritem za množenje matrik je tehnika deli in vladaj, ki zmanjša število množenj, potrebnih za velike matrike, tako da matrike razdeli na manjše podmatrike in združi njihove produkte.
  • Težava z najbližjim parom: Problem najbližjega para vključuje iskanje dveh najbližjih točk v nizu točk v večdimenzionalnem prostoru. Algoritem deli in vladaj, kot je algoritem najbližjega para deli in vladaj, lahko učinkovito reši to težavo z rekurzivno delitvijo točk in združitvijo rešitev iz podproblemov.

Osnove algoritma deli in vladaj:

Standardni algoritmi vklopljeni Algoritem deli in vladaj :

  • Binarno iskanje
  • Spoji Razvrsti
  • Hitro razvrščanje
  • Izračunajte pow(x, n)
  • Karatsuba algoritem za hitro množenje
  • Strassenovo matrično množenje
  • Konveksna lupina (preprost algoritem razdeli in vladaj)
  • Algoritem Quickhull za konveksno lupino

Težave, ki temeljijo na binarnem iskanju:

  • Poiščite element vrha v dani matriki
  • Preverite element večine v razvrščenem nizu
  • K-ti element dveh razvrščenih nizov
  • Poiščite število ničel
  • Poiščite število vrtenja v matriki Rotated Sorted
  • Poiščite točko, kjer monotono naraščajoča funkcija prvič postane pozitivna
  • Mediana dveh razvrščenih nizov
  • Mediana dveh razvrščenih nizov različnih velikosti
  • Slikarjeva težava s particijo z uporabo binarnega iskanja

Vadite naloge na Algoritem deli in vladaj :

  • Kvadratni koren celega števila
  • Največ in najmanj matrike z uporabo najmanjšega števila primerjav
  • Poiščite frekvenco vsakega elementa v matriki z omejenim obsegom v manj kot O(n) času
  • Težava s ploščicami
  • Štetje inverzij
  • Problem Skyline
  • Iščite v 2D matriki, razvrščeni po vrsticah in stolpcih
  • Dodelite najmanjše število strani
  • Modularno potenciranje (moč v modularni aritmetiki)

Hitre povezave :

  • Naučite se podatkovne strukture in algoritmov | Vadnica DSA
  • 'Težave za vadbo' na razdeli in vladaj
  • 'Kvizi' o razdeli in vladaj