Razdeli in vladaj Algoritem je tehnika reševanja problemov, ki se uporablja za reševanje problemov tako, da glavni problem razdelimo na podprobleme, jih rešujemo posamezno in jih nato združimo, da najdemo rešitev prvotnega problema. V tem članku bomo razpravljali o tem, kako je algoritem razdeli in vladaj koristen in kako ga lahko uporabimo za reševanje težav.

Kazalo

• Definicija algoritma deli in vladaj
• Delovanje algoritma deli in vladaj
• Značilnosti algoritma deli in vladaj
• Primeri algoritma deli in vladaj
• Analiza kompleksnosti algoritma deli in vladaj
• Uporaba algoritma deli in vladaj
• Prednosti algoritma deli in vladaj
• Slabosti algoritma deli in vladaj

Razdeli in vladaj Definicija algoritma:

Algoritem deli in vladaj vključuje razdelitev večjega problema na manjše podprobleme, njihovo neodvisno reševanje in nato združevanje njihovih rešitev za rešitev prvotnega problema. Osnovna ideja je rekurzivno razdeliti problem na manjše podprobleme, dokler ne postanejo dovolj preprosti, da jih je mogoče neposredno rešiti. Ko so rešitve za podprobleme pridobljene, se nato združijo v skupno rešitev.

Delovanje algoritma deli in vladaj:

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

q4 mesece

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.

Značilnosti algoritma razdeli in vladaj:

Algoritem razdeli in vladaj vključuje razdelitev problema na manjše, bolj obvladljive dele, reševanje vsakega dela posebej in nato združevanje rešitev za rešitev prvotnega problema. Značilnosti algoritma deli in vladaj so:

• Razdelitev problema : Prvi korak je razdelitev problema na manjše, bolj obvladljive podprobleme. To delitev je mogoče izvesti rekurzivno, dokler podproblemi ne postanejo dovolj preprosti za neposredno reševanje.
• Neodvisnost podproblemov : Vsak podproblem mora biti neodvisen od drugih, kar pomeni, da rešitev enega podproblema ni odvisna od rešitve drugega. To omogoča vzporedno obdelavo ali sočasno izvajanje podproblemov, kar lahko privede do povečanja učinkovitosti.
• Premagovanje vsake podprobleme : Ko so razdeljeni, se podproblemi rešujejo posamično. To lahko vključuje uporabo istega pristopa deli in vladaj rekurzivno, dokler podproblemi ne postanejo dovolj preprosti za neposredno reševanje, ali pa lahko vključuje uporabo drugačnega algoritma ali tehnike.
• Združevanje rešitev : Po rešitvi podproblemov se njihove rešitve združijo, da dobimo rešitev prvotnega problema. Ta kombinirani korak bi moral biti razmeroma učinkovit in enostaven, saj bi morale biti rešitve za podprobleme zasnovane tako, da se neopazno prilegajo.

Primeri algoritma deli in vladaj:

1. Iskanje največjega elementa v matriki:

Algoritem razdeli in vladaj lahko uporabimo za iskanje največjega elementa v matriki tako, da matriko razdelimo na dve enako veliki podnizici, največ teh dveh posameznih polovic pa najdemo tako, da ju ponovno razdelimo na dve manjši polovici. To se izvaja, dokler ne dosežemo podnizov velikosti 1. Ko dosežemo elemente, vrnemo največji element in združimo podnize tako, da vrnemo največ v vsakem podnizu.

// function to find the maximum no. // in a given array. int findMax(int a[], int lo, int hi) {  // If lo becomes greater than hi, then return minimum  // integer possible  if (lo>hi) vrni INT_MIN;  // Če ima podmatrika samo en element, vrni // element if (lo == hi) return a[lo];  int mid = (lo + hi) / 2;  // Pridobi največji element iz leve polovice int leftMax = findMax(a, lo, mid);  // Pridobi največji element z desne polovice int rightMax = findMax(a, mid + 1, hi);  // Vrne največji element z leve in desne // polovica vrne max(leftMax, rightMax); }>

// Function to find the maximum number // in a given array. static int findMax(int[] a, int lo, int hi) {  // If lo becomes greater than hi, then return  // minimum integer possible  if (lo>hi) vrni Integer.MIN_VALUE;  // Če ima podmatrika samo en element, vrni // element if (lo == hi) return a[lo];  int mid = (lo + hi) / 2;  // Pridobi največji element iz leve polovice int leftMax = findMax(a, lo, mid);  // Pridobi največji element z desne polovice int rightMax = findMax(a, mid + 1, hi);  // Vrni največji element z leve in // desne polovice return Math.max(leftMax, rightMax); }>

# Function to find the maximum number # in a given array. def find_max(a, lo, hi): # If lo becomes greater than hi, then return minimum # integer possible if lo>hi: return float('-inf') # Če ima podmatrika samo en element, vrni element # if lo == hi: return a[lo] mid = (lo + hi) // 2 # Dobi največ element z leve polovice left_max = find_max(a, lo, mid) # Pridobi največji element z desne polovice right_max = find_max(a, mid + 1, hi) # Vrni največji element z leve in desne # polovica vrne max (levo_max, desno_max)>

// Function to find the maximum number // in a given array. static int FindMax(int[] a, int lo, int hi) {  // If lo becomes greater than hi, then return  // minimum integer possible  if (lo>hi) vrni int.MinValue;  // Če ima podmatrika samo en element, vrni // element if (lo == hi) return a[lo];  int mid = (lo + hi) / 2;  // Pridobi največji element iz leve polovice int leftMax = FindMax(a, lo, mid);  // Pridobi največji element z desne polovice int rightMax = FindMax(a, mid + 1, hi);  // Vrni največji element z leve in // desne polovice return Math.Max(leftMax, rightMax); }>

// Function to find the maximum number // in a given array. function findMax(a, lo, hi) {  // If lo becomes greater than hi, then return minimum  // integer possible  if (lo>hi) vrni Number.MIN_VALUE;  // Če ima podmatrika samo en element, vrni // element if (lo === hi) return a[lo];  const mid = Math.floor((lo + hi) / 2);  // Pridobi največji element iz leve polovice const leftMax = findMax(a, lo, mid);  // Pridobi največji element iz desne polovice const rightMax = findMax(a, mid + 1, hi);  // Vrne največji element z leve in desne // polovica vrne Math.max(leftMax, rightMax); }>

2. Iskanje najmanjšega elementa v matriki:

Podobno lahko uporabimo algoritem razdeli in vladaj, da poiščemo najmanjši element v matriki tako, da matriko razdelimo na dve enako veliki podnizici, pri čemer poiščemo najmanjšo vrednost teh dveh posameznih polovic tako, da ju ponovno razdelimo na dve manjši polovici. To se izvaja, dokler ne dosežemo podnizov velikosti 1. Ko dosežemo elemente, vrnemo najmanjši element in združimo podnize tako, da vrnemo minimum v vsakem podnizu.

sklad v ds

3. Spoji Razvrsti:

Algoritem razdeli in vladaj lahko uporabimo za razvrščanje matrike v naraščajočem ali padajočem vrstnem redu, tako da matriko razdelimo na manjše podmatrike, razvrstimo manjše podmatrike in nato združimo razvrščene matrike, da razvrstimo izvirno matriko.

Analiza kompleksnosti algoritma deli in vladaj:

T(n) = aT(n/b) + f(n), kjer je n = velikost vnosa a = število podproblemov v rekurziji, n/b = velikost vsakega podproblema. Predpostavlja se, da imajo vsi podproblemi enako velikost. f(n) = stroški dela, opravljenega zunaj rekurzivnega klica, ki vključujejo stroške delitve problema in stroške združevanja rešitev

Uporaba algoritma deli in vladaj:

Sledi nekaj standardnih algoritmov, ki sledijo algoritmu razdeli in vladaj:

• Hitro razvrščanje je algoritem za razvrščanje, ki izbere vrtilni element in prerazporedi elemente matrike tako, da se vsi elementi, manjši od izbranega vrtilnega elementa, premaknejo na levo stran vrtišča, vsi večji elementi pa se premaknejo na desno stran. Na koncu algoritem rekurzivno razvrsti podnize na levi in ​​desni strani vrtilnega elementa.
• Spoji Razvrsti je tudi algoritem za razvrščanje. Algoritem matriko razdeli na dve polovici, ju rekurzivno razvrsti in na koncu obe razvrščeni polovici združi.
• Najbližji par točk Težava je najti najbližji par točk v nizu točk v ravnini x-y. Težavo je mogoče rešiti v O(n^2) času z izračunom razdalj vsakega para točk in primerjavo razdalj, da bi našli najmanjšo. Algoritem razdeli in vladaj reši problem v O(N log N) času.
• Strassenov algoritem je učinkovit algoritem za množenje dveh matrik. Preprosta metoda za množenje dveh matrik potrebuje 3 ugnezdene zanke in je O(n^3). Strassenov algoritem pomnoži dve matriki v O(n^2,8974) času.
• Cooley–Tukeyjev algoritem za hitro Fourierjevo transformacijo (FFT). je najpogostejši algoritem za FFT. Je algoritem deli in vladaj, ki deluje v O(N log N) času.
• Karatsuba algoritem za hitro množenje naredi množenje dveh binarnih nizov v O(n^1.59), kjer je n dolžina binarnega niza.

Prednosti algoritma deli in vladaj:

• Reševanje težkih problemov: Tehnika deli in vladaj je orodje za konceptualno reševanje težkih problemov. npr. Uganka Hanojski stolp. Zahteva način razdelitve problema na podprobleme in reševanje vseh kot posamezne primere ter nato združevanje podproblemov v prvotni problem.
• Učinkovitost algoritma: Algoritem deli in vladaj pogosto pomaga pri odkrivanju učinkovitih algoritmov. Je ključ do algoritmov, kot sta Hitro razvrščanje in Razvrščanje z združitvijo, ter hitre Fourierove transformacije.
• Vzporednost: Običajno se algoritmi razdeli in vladaj uporabljajo v večprocesorskih strojih, ki imajo sisteme s skupnim pomnilnikom, kjer komunikacije podatkov med procesorji ni treba načrtovati vnaprej, ker se lahko različne podprobleme izvajajo na različnih procesorjih.
• Dostop do pomnilnika: Ti algoritmi seveda učinkovito uporabljajo predpomnilnike pomnilnika. Ker so podproblemi dovolj majhni, da jih je mogoče rešiti v predpomnilniku brez uporabe glavnega pomnilnika, ki je počasnejši. Vsak algoritem, ki učinkovito uporablja predpomnilnik, se imenuje pozaba predpomnilnika.

Slabosti algoritma deli in vladaj:

• režijski stroški: Postopek razdelitve problema na podprobleme in nato združevanje rešitev lahko zahteva dodaten čas in sredstva. Ta režijski strošek je lahko pomemben za probleme, ki so že relativno majhni ali imajo preprosto rešitev.
• Kompleksnost: Razdelitev problema na manjše podprobleme lahko poveča kompleksnost celotne rešitve. To še posebej velja, kadar so podproblemi soodvisni in jih je treba rešiti v določenem vrstnem redu.
• Težavnost izvedbe: Nekatere probleme je težko razdeliti na manjše podprobleme ali pa je za to potreben zapleten algoritem. V teh primerih je uvedba rešitve deli in vladaj lahko izziv.
• Omejitve pomnilnika: Pri delu z velikimi nabori podatkov lahko pomnilniške zahteve za shranjevanje vmesnih rezultatov podproblemov postanejo omejevalni dejavnik.

Pogosto zastavljena vprašanja (FAQ) o algoritmu deli in vladaj:

1. Kaj je algoritem razdeli in vladaj?

Deli in vladaj je tehnika reševanja problemov, pri kateri se problem razdeli na manjše, bolj obvladljive podprobleme. Ti podproblemi se rešujejo rekurzivno, nato pa se njihove rešitve združijo za rešitev prvotnega problema.

2. Kateri so ključni koraki, vključeni v algoritem deli in vladaj?

Glavni koraki so:

program java hello

Razdeli : Težavo razdelite na manjše podprobleme.

osvojiti : Podprobleme rešite rekurzivno.

Združite : Združite ali združite rešitve podproblemov, da dobite rešitev prvotnega problema.

3. Kateri so primeri problemov, rešenih z uporabo razdeli in vladaj?

Algoritem razdeli in vladaj se uporablja pri algoritmih razvrščanja, kot sta razvrščanje z združitvijo in hitro razvrščanje, iskanje najbližjega para točk, Strassenov algoritem itd.

4. Kako Merge Sort uporablja pristop razdeli in vladaj?

Razvrščanje z združitvijo razdeli matriko na dve polovici, rekurzivno razvrsti vsako polovico in nato združi razvrščeni polovici, da ustvari končno razvrščeno matriko.

normalne oblike

5. Kakšna je časovna kompleksnost algoritmov razdeli in vladaj?

Časovna zahtevnost se razlikuje glede na specifičen problem in način izvajanja. Na splošno ima veliko algoritmov razdeli in vladaj časovno kompleksnost O(n log n) ali večjo.

6. Ali je mogoče algoritme razdeli in vladaj vzporediti?

Da, algoritme razdeli in vladaj je pogosto naravno vzporedno, ker je mogoče sočasno reševati neodvisne podprobleme. Zaradi tega so primerni za vzporedna računalniška okolja.

7. Katere so nekatere strategije za izbiro osnovnega primera v algoritmih razdeli in vladaj?

Osnovni primer mora biti dovolj preprost za neposredno reševanje, brez nadaljnje delitve. Pogosto se izbere na podlagi najmanjše velikosti vnosa, kjer je težavo mogoče rešiti trivialno.

myflixr

8. Ali obstajajo kakšne pomanjkljivosti ali omejitve pri uporabi razdeli in vladaj?

Čeprav lahko Deli in vladaj vodi do učinkovitih rešitev za številne težave, morda ni primeren za vse vrste težav. Stroški zaradi rekurzije in združevanja rešitev so lahko tudi zaskrbljujoči pri zelo velikih problemih.

9. Kako analizirate prostorsko kompleksnost algoritmov razdeli in vladaj?

Kompleksnost prostora je odvisna od dejavnikov, kot sta globina rekurzije in pomožni prostor, potreben za kombiniranje rešitev. Analiza kompleksnosti prostora običajno vključuje upoštevanje prostora, ki ga uporablja vsak rekurzivni klic.

10. Katere so nekatere skupne prednosti algoritma deli in vladaj?

Algoritem deli in vladaj ima številne prednosti. Nekateri med njimi vključujejo:

• Reševanje težkih problemov
• Učinkovitost algoritma
• Paralelizem
• Dostop do pomnilnika

Deli in vladaj je priljubljena algoritemska tehnika v računalništvu, ki vključuje razčlenitev problema na manjše podprobleme, reševanje vsakega podproblema neodvisno in nato združevanje rešitev podproblemov za rešitev prvotnega problema. Osnovna ideja te tehnike je razdeliti problem na manjše, bolj obvladljive podprobleme, ki jih je lažje rešiti.