Skaldyk ir valdyk Algoritmas yra problemų sprendimo technika, naudojama problemoms spręsti, padalijant pagrindinę problemą į subproblemas, sprendžiant jas atskirai ir sujungiant, kad būtų rastas pradinės problemos sprendimas. Šiame straipsnyje aptarsime, kaip „Skaldyk ir užkariauk“ algoritmas yra naudingas ir kaip galime jį panaudoti problemoms spręsti.

Turinys

• „Skaldyk ir užkariauk“ algoritmo apibrėžimas
• Skaldyk ir valdyk algoritmo veikimas
• Algoritmo „Skaldyk ir valdyk“ charakteristikos
• Skaldyk ir valdyk algoritmo pavyzdžiai
• „Skaldyk ir valdyk“ algoritmo sudėtingumo analizė
• Skaldyk ir valdyk algoritmo taikymai
• Algoritmo „Skaldyk ir valdyk“ pranašumai
• Algoritmo „Skaldyk ir valdyk“ trūkumai

Skaldyk ir valdyk Algoritmo apibrėžimas:

Skaldyk ir užkariauk algoritmas apima didesnės problemos suskaidymą į smulkesnes problemas, jų savarankišką sprendimą ir jų sprendimų derinimą, kad išspręstų pradinę problemą. Pagrindinė idėja yra rekursyviai padalinti problemą į mažesnes dalis, kol jos taps pakankamai paprastos, kad būtų galima išspręsti tiesiogiai. Gavus subproblemų sprendimus, jie sujungiami ir gaunamas bendras sprendimas.

Skaldyk ir valdyk algoritmo veikimas:

„Skaldyk ir užkariauk“ algoritmą galima suskirstyti į tris etapus: Padalinti , Užkariauti ir Sujungti .

ankita lokhande amžius

1. Padalinkite:

• Suskaidykite pradinę problemą į mažesnes problemas.
• Kiekviena subproblema turėtų būti bendros problemos dalis.
• Tikslas yra padalinti problemą tol, kol nebebus įmanoma skaidyti.

2. Užkariauti:

• Išspręskite kiekvieną smulkesnę užduotį atskirai.
• Jei subproblema yra pakankamai maža (dažnai vadinama baziniu atveju), mes ją išsprendžiame tiesiogiai, be tolesnių pasikartojimų.
• Tikslas yra savarankiškai rasti šių subproblemų sprendimus.

3. Sujungti:

• Sujunkite antrines problemas, kad gautumėte galutinį visos problemos sprendimą.
• Išsprendę mažesnes subproblemas, mes rekursyviai sujungiame jų sprendimus, kad gautume didesnės problemos sprendimą.
• Tikslas yra suformuluoti pradinės problemos sprendimą, sujungiant subproblemų rezultatus.

Skaldyk ir valdyk algoritmo ypatybės:

„Skaldyk ir užkariauk“ algoritmas apima problemos suskaidymą į mažesnes, lengviau valdomas dalis, kiekvienos dalies išsprendimą atskirai ir sprendimų derinimą, kad išspręstų pradinę problemą. „Skaldyk ir valdyk“ algoritmo ypatybės yra šios:

• Problemos padalijimas : Pirmas žingsnis yra padalinti problemą į mažesnes, lengviau valdomas problemas. Šį padalijimą galima atlikti rekursyviai, kol subproblemos tampa pakankamai paprastos, kad jas būtų galima išspręsti tiesiogiai.
• Subproblemų nepriklausomumas : Kiekviena poproblema turi būti nepriklausoma nuo kitų, tai reiškia, kad vienos subproblemos sprendimas nepriklauso nuo kitos. Tai leidžia lygiagrečiai apdoroti arba vienu metu vykdyti subproblemas, o tai gali padidinti efektyvumą.
• Kiekvienos subproblemos įveikimas : Padalijus, antrinės problemos išsprendžiamos atskirai. Tai gali apimti tą patį „skaldyk ir valdyk“ metodo taikymą rekursyviai, kol subproblemos taps pakankamai paprastos, kad jas būtų galima išspręsti tiesiogiai, arba gali prireikti taikyti kitokį algoritmą ar metodą.
• Sprendimų derinimas : Išsprendus subproblemas, jų sprendimai sujungiami ir gaunamas pradinės problemos sprendimas. Šis derinimo žingsnis turėtų būti gana efektyvus ir paprastas, nes subproblemų sprendimai turėtų būti sukurti taip, kad jie sklandžiai derėtų.

Skaldyk ir valdyk algoritmo pavyzdžiai:

1. Raskite maksimalų elementą masyve:

Galime naudoti „Skaldyk ir užkariauk“ algoritmą, kad surastume maksimalų masyvo elementą, padalydami masyvą į dvi vienodo dydžio pogrupius, o didžiausią iš šių dviejų atskirų dalių rastume dar kartą padalydami jas į dvi mažesnes dalis. Tai daroma tol, kol pasiekiame 1 dydžio pogrupius. Pasiekę elementus grąžiname maksimalų elementą ir sujungiame poskyris, grąžindami maksimumą kiekviename poblokyje.

// 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>labas) grįžti INT_MIN;  // Jei pogrupyje yra tik vienas elementas, grąžinkite // elementą if (lo == hi) return a[lo];  int mid = (lo + hi) / 2;  // Gauti maksimalų elementą iš kairės pusės int leftMax = findMax(a, lo, mid);  // Gauti maksimalų elementą iš dešinės pusės int rightMax = findMax(a, mid + 1, hi);  // Grąžina maksimalų elementą iš kairės ir dešinės // half return 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) grąžinti Integer.MIN_VALUE;  // Jei pogrupyje yra tik vienas elementas, grąžinkite // elementą if (lo == hi) return a[lo];  int mid = (lo + hi) / 2;  // Gauti maksimalų elementą iš kairės pusės int leftMax = findMax(a, lo, mid);  // Gauti maksimalų elementą iš dešinės pusės int rightMax = findMax(a, mid + 1, hi);  // Grąžina maksimalų elementą iš kairės ir // dešinės pusės 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') # Jei pogrupyje yra tik vienas elementas, grąžinkite # elementą, jei lo == hi: return a[lo] mid = (lo + hi) // 2 # Gaukite didžiausią elementas iš kairės pusės left_max = find_max(a, lo, mid) # Gauti maksimalų elementą iš dešinės pusės right_max = find_max(a, mid + 1, hi) # Grąžinti maksimalų elementą iš kairės ir dešinės # half return max (left_max, right_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) return int.MinValue;  // Jei pogrupyje yra tik vienas elementas, grąžinkite // elementą if (lo == hi) return a[lo];  int mid = (lo + hi) / 2;  // Gauti maksimalų elementą iš kairės pusės int leftMax = FindMax(a, lo, mid);  // Gauti maksimalų elementą iš dešinės pusės int rightMax = FindMax(a, mid + 1, hi);  // Grąžina maksimalų elementą iš kairės ir // dešinės pusės grąžinimas 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) grąžinti Number.MIN_VALUE;  // Jei pogrupyje yra tik vienas elementas, grąžinkite // elementą if (lo === hi) return a[lo];  const mid = Math.floor((lo + hi) / 2);  // Gauti maksimalų elementą iš kairės pusės const leftMax = findMax(a, lo, mid);  // Gauti maksimalų elementą iš dešinės pusės const rightMax = findMax(a, mid + 1, hi);  // Grąžina maksimalų elementą iš kairės ir dešinės // half return Math.max(leftMax, rightMax); }>

2. Raskite mažiausią elementą masyve:

Panašiai galime naudoti „Skaldyti ir užkariauti“ algoritmą, kad surastume mažiausią elementą masyve, padalydami masyvą į dvi vienodo dydžio pogrupius, o šių dviejų atskirų dalių minimumą surasdami dar kartą padalydami jas į dvi mažesnes dalis. Tai daroma tol, kol pasiekiame 1 dydžio pogrupius. Pasiekę elementus, grąžiname minimalų elementą ir sujungiame poskyris, grąžindami minimumą kiekviename poblokyje.

3. Sujungti rūšiavimą:

Galime naudoti „Skaldyti ir užkariauti“ algoritmą, norėdami surūšiuoti masyvą didėjančia arba mažėjančia tvarka, padalydami masyvą į mažesnius pogrupius, surūšiuodami mažesnius ir sujungdami surūšiuotus masyvus, kad surūšiuotumėte pradinį masyvą.

„Skaldyk ir valdyk“ algoritmo sudėtingumo analizė:

T(n) = aT(n/b) + f(n), kur n = įvesties dydis a = subproblemų skaičius rekursijoje n/b = kiekvienos poproblemos dydis. Manoma, kad visos antrinės problemos yra vienodo dydžio. f(n) = ne rekursinio skambučio atlikto darbo kaina, kuri apima problemos padalijimo ir sprendimų sujungimo išlaidas

„Skaldyk ir valdyk“ algoritmo taikymas:

Toliau pateikiami keli standartiniai algoritmai, kurie vadovaujasi „Skaldyk ir užkariauk“ algoritmu:

• Greitas rūšiavimas yra rūšiavimo algoritmas, kuris parenka sukimo elementą ir pertvarko masyvo elementus taip, kad visi elementai, mažesni už pasirinktą sukimosi elementą, judėtų į kairę sukimosi pusę, o visi didesni elementai – į dešinę. Galiausiai, algoritmas rekursyviai rūšiuoja sukamojo elemento kairėje ir dešinėje esančias pogrupes.
• Sujungti Rūšiuoti taip pat yra rūšiavimo algoritmas. Algoritmas padalija masyvą į dvi dalis, jas rekursyviai surūšiuoja ir galiausiai sujungia dvi surūšiuotas puses.
• Artimiausia taškų pora Problema yra rasti artimiausią taškų porą taškų rinkinyje x-y plokštumoje. Uždavinys gali būti išspręstas per O(n^2) laiką, apskaičiuojant kiekvienos taškų poros atstumus ir lyginant atstumus, kad būtų nustatytas minimumas. „Skaldyk ir valdyk“ algoritmas išsprendžia problemą per O(N log N) laiką.
• Strasseno algoritmas yra efektyvus dviejų matricų padauginimo algoritmas. Paprastam dviejų matricų padauginimo metodui reikia 3 įdėtų kilpų ir yra O(n^3). Strasseno algoritmas padaugina dvi matricas per O(n^2.8974) laiką.
• Cooley–Tukey greitojo Furjė transformacijos (FFT) algoritmas yra labiausiai paplitęs FFT algoritmas. Tai dalyk ir užkariauk algoritmas, veikiantis O (N log N) laiku.
• Karatsuba algoritmas greitam dauginimui padaugina dvi dvejetaines eilutes iš O(n^1.59) kur n yra dvejetainės eilutės ilgis.

„Skaldyk ir valdyk“ algoritmo pranašumai:

• Sudėtingų problemų sprendimas: „Skaldyk ir valdyk“ technika – tai įrankis, padedantis konceptualiai spręsti sudėtingas problemas. pvz. Hanojaus bokšto galvosūkis. Tam reikia būdo, kaip problemą suskaidyti į poproblemas ir visas jas išspręsti kaip atskirus atvejus, o paskui sujungti subproblemas su pradine problema.
• Algoritmo efektyvumas: Skaldyk ir valdyk algoritmas dažnai padeda atrasti efektyvius algoritmus. Tai yra raktas į tokius algoritmus kaip greitas rūšiavimas ir sujungimo rūšiavimas bei greitos Furjė transformacijos.
• Lygiagretumas: Įprastai Divide and Conquer algoritmai naudojami kelių procesorių mašinose, turinčiose bendros atminties sistemas, kur duomenų perdavimo tarp procesorių nereikia planuoti iš anksto, nes skirtinguose procesoriuose gali būti įvykdytos skirtingos antrinės problemos.
• Prieiga prie atminties: Šie algoritmai natūraliai efektyviai išnaudoja atminties talpyklas. Kadangi antrinės problemos yra pakankamai mažos, kad jas būtų galima išspręsti talpykloje, nenaudojant pagrindinės atminties, kuri yra lėtesnė. Bet koks algoritmas, kuris efektyviai naudoja talpyklą, vadinamas nepastebėtu talpyklos.

„Skaldyk ir valdyk“ algoritmo trūkumai:

• Papildomos išlaidos: Problemos padalijimas į subproblemas ir sprendimų derinimas gali pareikalauti papildomo laiko ir išteklių. Šios pridėtinės išlaidos gali būti reikšmingos problemoms, kurios jau yra palyginti nedidelės arba kurios turi paprastą sprendimą.
• Sudėtingumas: Problemos padalijimas į smulkesnes dalis gali padidinti bendro sprendimo sudėtingumą. Tai ypač aktualu, kai subproblemos yra tarpusavyje susijusios ir turi būti sprendžiamos tam tikra tvarka.
• Įgyvendinimo sunkumas: Kai kurias problemas sunku suskirstyti į smulkesnes problemas arba tam reikia sudėtingo algoritmo. Tokiais atvejais gali būti sudėtinga įgyvendinti „skaldyk ir valdyk“ sprendimą.
• Atminties apribojimai: Dirbant su dideliais duomenų rinkiniais, ribojančiu veiksniu gali tapti atminties poreikiai, skirti saugoti tarpinius subproblemų rezultatus.

Dažnai užduodami klausimai (DUK) apie „Skaldyk ir valdyk“ algoritmą:

1. Kas yra „Skaldyk ir valdyk“ algoritmas?

„Skaldyk ir valdyk“ – tai problemų sprendimo technika, kai problema suskirstoma į mažesnes, lengviau valdomas subproblemas. Šios antrinės problemos išsprendžiamos rekursyviai, o tada jų sprendimai sujungiami, kad būtų išspręsta pradinė problema.

2. Kokie yra pagrindiniai algoritmo „Skaldyk ir valdyk“ žingsniai?

Pagrindiniai žingsniai yra šie:

Padalinti : suskaidykite problemą į smulkesnes dalis.

Užkariauti : Rekursyviai išspręskite subproblemas.

Sujungti : sujunkite arba sujunkite subproblemų sprendimus, kad gautumėte pradinės problemos sprendimą.

3. Kokie yra problemų, išspręstų naudojant „Skaldyk ir valdyk“, pavyzdžiai?

„Skaldyk ir užkariauk“ algoritmas naudojamas rūšiuojant tokius algoritmus kaip „Merge Sort“ ir „Quick Sort“, surandant artimiausią taškų porą, Strasseno algoritmą ir kt.

4. Kaip „Sujungimo rūšiavimas“ naudoja „Skaldyk ir valdyk“ metodą?

Sujungimo rūšiavimas padalija masyvą į dvi dalis, rekursyviai surūšiuoja kiekvieną pusę, o tada sujungia surūšiuotas puses, kad gautų galutinį surūšiuotą masyvą.

5. Koks yra „Skaldyk ir valdyk“ algoritmų sudėtingumas laikui bėgant?

Laiko sudėtingumas skiriasi priklausomai nuo konkrečios problemos ir jos įgyvendinimo. Paprastai daugelio „Skaldyk ir valdyk“ algoritmų laiko sudėtingumas yra O(n log n) arba geresnis.

6. Ar „Skaldyk ir užkariauk“ algoritmus galima lygiagretinti?

Taip, „Skaldyk ir užkariauk“ algoritmai dažnai yra natūraliai lygiagretinami, nes nepriklausomos antrinės problemos gali būti sprendžiamos vienu metu. Dėl to jie tinka lygiagrečioms skaičiavimo aplinkoms.

7. Kokios yra pagrindinės atvejo pasirinkimo strategijos „Skaldyk ir valdyk“ algoritmuose?

Bazinis atvejis turėtų būti pakankamai paprastas, kad jį būtų galima išspręsti tiesiogiai, be tolesnio skirstymo. Jis dažnai pasirenkamas pagal mažiausią įvesties dydį, kai problemą galima išspręsti trivialiai.

debesų kompiuterijos programos

8. Ar yra kokių nors trūkumų ar apribojimų naudojant „Skaldyk ir valdyk“?

Nors „Skaldyk ir valdyk“ gali padėti rasti efektyvius daugelio problemų sprendimus, ji gali būti netinkama visų tipų problemoms spręsti. Pridėtinės išlaidos dėl rekursijos ir sprendimų derinimo taip pat gali kelti susirūpinimą dėl labai didelių problemų.

9. Kaip analizuojate „Skaldyk ir valdyk“ algoritmų erdvės sudėtingumą?

Erdvės sudėtingumas priklauso nuo tokių veiksnių kaip rekursijos gylis ir pagalbinė erdvė, reikalinga sprendimams derinti. Erdvės sudėtingumo analizė paprastai apima kiekvieno rekursinio skambučio naudojamą erdvę.

10. Kokie yra bendri „Skaldyk ir valdyk“ algoritmo pranašumai?

„Skaldyk ir valdyk“ algoritmas turi daug privalumų. Kai kurie iš jų apima:

• Sunkių problemų sprendimas
• Algoritmo efektyvumas
• Lygiagretumas
• Prieiga prie atminties

„Skaldyk ir valdyk“ yra populiari kompiuterių mokslo algoritminė technika, kuri apima problemos suskaidymą į smulkesnes problemas, kiekvienos poproblemos sprendimą atskirai, o tada sujungiant antrinių problemų sprendimus, kad būtų išspręsta pradinė problema. Pagrindinė šios technikos idėja yra padalinti problemą į mažesnes, lengviau valdomas problemas, kurias galima lengviau išspręsti.