Skaldi un iekaro Algoritms ir problēmu risināšanas paņēmiens, ko izmanto problēmu risināšanai, sadalot galveno problēmu apakšproblēmās, risinot tās atsevišķi un pēc tam apvienojot, lai atrastu sākotnējās problēmas risinājumu. Šajā rakstā mēs apspriedīsim, kā sadalīšanas un iekarošanas algoritms ir noderīgs un kā mēs varam to izmantot problēmu risināšanai.

Satura rādītājs

• Dali un iekaro algoritma definīcija
• Skaldi un valdi algoritma darbība
• Skaldi un valdi algoritma raksturojums
• Skaldi un valdi algoritma piemēri
• Skaldi un valdi algoritma sarežģītības analīze
• Skaldi un valdi algoritma pielietojumi
• Skaldi un iekaro algoritma priekšrocības
• Skaldi un valdi algoritma trūkumi

Skaldi un iekaro Algoritma definīcija:

Dali un iekaro algoritms ietver lielākas problēmas sadalīšanu mazākās apakšproblēmās, to atrisināšanu neatkarīgi un to risinājumu apvienošanu, lai atrisinātu sākotnējo problēmu. Pamatideja ir rekursīvi sadalīt problēmu mazākās apakšproblēmās, līdz tās kļūst pietiekami vienkāršas, lai tās atrisinātu tieši. Kad apakšproblēmu risinājumi ir iegūti, tie tiek apvienoti, lai iegūtu kopējo risinājumu.

Skaldi un valdi algoritma darbība:

Sadalīšanas un iekarošanas algoritmu var iedalīt trīs posmos: Sadaliet , Iekarot un Apvienot .

0,06 kā daļu

1. Sadaliet:

• Sadaliet sākotnējo problēmu mazākās apakšproblēmās.
• Katrai apakšproblēmai ir jāatspoguļo daļa no kopējās problēmas.
• Mērķis ir sadalīt problēmu, līdz tālāka sadalīšana nav iespējama.

2. Iekarot:

• Atrisiniet katru no mazākajām apakšproblēmām atsevišķi.
• Ja apakšproblēma ir pietiekami maza (bieži saukta par pamatgadījumu), mēs to atrisinām tieši bez turpmākas atkārtošanās.
• Mērķis ir patstāvīgi rast risinājumus šīm apakšproblēmām.

3. Apvienot:

• Apvienojiet apakšproblēmas, lai iegūtu visas problēmas galīgo risinājumu.
• Kad mazākās apakšproblēmas ir atrisinātas, mēs rekursīvi apvienojam to risinājumus, lai iegūtu lielākas problēmas risinājumu.
• Mērķis ir formulēt sākotnējās problēmas risinājumu, apvienojot apakšproblēmu rezultātus.

Skaldi un valdi algoritma raksturojums:

Sadalīšanas un iekarošanas algoritms ietver problēmas sadalīšanu mazākās, vieglāk pārvaldāmās daļās, katras daļas atrisināšanu atsevišķi un risinājumu apvienošanu, lai atrisinātu sākotnējo problēmu. Skaldi un iekaro algoritmam ir šādas īpašības:

• Problēmas sadalīšana : pirmais solis ir sadalīt problēmu mazākās, vieglāk pārvaldāmās apakšproblēmās. Šo sadalīšanu var veikt rekursīvi, līdz apakšproblēmas kļūst pietiekami vienkāršas, lai tās atrisinātu tieši.
• Apakšproblēmu neatkarība : Katrai apakšproblēmai jābūt neatkarīgai no pārējām, kas nozīmē, ka vienas apakšproblēmas risināšana nav atkarīga no citas. Tas ļauj veikt paralēlu apstrādi vai vienlaicīgu apakšproblēmu izpildi, kas var palielināt efektivitāti.
• Katras apakšproblēmas pārvarēšana : pēc sadalīšanas apakšproblēmas tiek atrisinātas atsevišķi. Tas var ietvert vienas un tās pašas sadali un valdi pieejas piemērošanu rekursīvi, līdz apakšproblēmas kļūst pietiekami vienkāršas, lai tās atrisinātu tieši, vai arī cita algoritma vai tehnikas pielietošana.
• Risinājumu apvienošana : Pēc apakšproblēmu atrisināšanas to risinājumi tiek apvienoti, lai iegūtu sākotnējās problēmas risinājumu. Šim kombinācijas posmam jābūt salīdzinoši efektīvam un vienkāršam, jo ​​apakšproblēmu risinājumiem jābūt izstrādātiem tā, lai tie nevainojami saskanētu.

Skaldi un valdi algoritma piemēri:

1. Maksimālā elementa atrašana masīvā:

Mēs varam izmantot sadalīšanas un iekarošanas algoritmu, lai atrastu maksimālo elementu masīvā, sadalot masīvu divos vienāda lieluma apakšblokos, atrodot maksimālo no šīm divām atsevišķām pusēm, atkal sadalot tās divās mazākās daļās. Tas tiek darīts, līdz tiek sasniegti 1. izmēra apakšbloki. Pēc elementu sasniegšanas mēs atgriežam maksimālo elementu un apvienojam apakšblokus, atgriežot maksimālo katrā apakšmasīvā.

// 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>sveiki) atgriezties INT_MIN;  // Ja apakšmasīvā ir tikai viens elements, atgriež // elementu if (lo == hi) return a[lo];  int mid = (lo + hi) / 2;  // Iegūt maksimālo elementu no kreisās puses int leftMax = findMax(a, lo, mid);  // Iegūt maksimālo elementu no labās puses int rightMax = findMax(a, mid + 1, hi);  // Atgriezt maksimālo elementu no kreisās un labās puses // 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) atgriež Vesels skaitlis.MIN_VALUE;  // Ja apakšmasīvā ir tikai viens elements, atgriež // elementu if (lo == hi) return a[lo];  int mid = (lo + hi) / 2;  // Iegūt maksimālo elementu no kreisās puses int leftMax = findMax(a, lo, mid);  // Iegūt maksimālo elementu no labās puses int rightMax = findMax(a, mid + 1, hi);  // Atgriezt maksimālo elementu no kreisās puses un // labās puses atgriešana 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') # Ja apakšmasīvā ir tikai viens elements, atgriež # elementu if lo == hi: return a[lo] mid = (lo + hi) // 2 # Iegūt maksimālo elements no kreisās puses left_max = find_max(a, lo, mid) # Iegūt maksimālo elementu no labās puses right_max = find_max(a, mid + 1, hi) # Atgriezt maksimālo elementu no kreisās un labās puses # 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;  // Ja apakšmasīvā ir tikai viens elements, atgriež // elementu if (lo == hi) return a[lo];  int mid = (lo + hi) / 2;  // Iegūt maksimālo elementu no kreisās puses int leftMax = FindMax(a, lo, mid);  // Iegūt maksimālo elementu no labās puses int rightMax = FindMax(a, mid + 1, hi);  // Atgriezt maksimālo elementu no kreisās puses un // labās puses atgriešana 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) atgriež Number.MIN_VALUE;  // Ja apakšmasīvā ir tikai viens elements, atgriež // elementu if (lo === hi) return a[lo];  const mid = Math.floor((lo + hi) / 2);  // Iegūstiet maksimālo elementu no kreisās puses const leftMax = findMax(a, lo, mid);  // Iegūt maksimālo elementu no labās puses const rightMax = findMax(a, mid + 1, hi);  // Atgriež maksimālo elementu no kreisās un labās puses // half return Math.max(leftMax, rightMax); }>

2. Minimālā elementa atrašana masīvā:

Līdzīgi mēs varam izmantot sadalīšanas un iekarošanas algoritmu, lai atrastu minimālo elementu masīvā, sadalot masīvu divos vienāda lieluma apakšblokos, atrodot minimālo no šīm divām atsevišķām pusēm, atkal sadalot tās divās mazākās daļās. Tas tiek darīts, līdz tiek sasniegti 1. izmēra apakšbloki. Pēc elementu sasniegšanas mēs atgriežam minimālo elementu un apvienojam apakšblokus, atgriežot minimālo katrā apakšmasīvā.

salīdzināt ar virkni

3. Sapludināt kārtot:

Mēs varam izmantot sadalīšanas un iekarošanas algoritmu, lai kārtotu masīvu augošā vai dilstošā secībā, sadalot masīvu mazākos apakšmasīvos, sašķirot mazākos apakšmasīvus un pēc tam sapludinot sakārtotos masīvus, lai sakārtotu sākotnējo masīvu.

Skaldi un valdi algoritma sarežģītības analīze:

T(n) = aT(n/b) + f(n), kur n = ievades lielums a = apakšproblēmu skaits rekursijā n/b = katras apakšproblēmas lielums. Tiek pieņemts, ka visām apakšproblēmām ir vienāds izmērs. f(n) = ārpus rekursīvā izsaukuma veiktā darba izmaksas, kas ietver problēmas sadalīšanas izmaksas un risinājumu apvienošanas izmaksas

Skaldi un valdi algoritma pielietojumi:

Tālāk ir minēti daži standarta algoritmi, kas seko sadalīšanas un iekarošanas algoritmam.

• Ātrā šķirošana ir kārtošanas algoritms, kas atlasa rakursa elementu un pārkārto masīva elementus tā, lai visi elementi, kas ir mazāki par atlasīto rakursa elementu, pārvietotos uz rakursa kreiso pusi un visi lielākie elementi pārvietotos uz labo pusi. Visbeidzot, algoritms rekursīvi kārto apakšmasīvus pa kreisi un pa labi no pagrieziena elementa.
• Sapludināt Kārtot ir arī šķirošanas algoritms. Algoritms sadala masīvu divās daļās, rekursīvi sašķiro tās un visbeidzot apvieno abas sakārtotās puses.
• Tuvākais punktu pāris Problēma ir atrast tuvāko punktu pāri punktu kopā x-y plaknē. Problēmu var atrisināt O(n^2) laikā, aprēķinot katra punktu pāra attālumus un salīdzinot attālumus, lai atrastu minimumu. Dalīšanas un iekarošanas algoritms problēmu atrisina O(N log N) laikā.
• Štrasena algoritms ir efektīvs algoritms divu matricu reizināšanai. Vienkāršai metodei divu matricu reizināšanai nepieciešamas 3 ligzdotas cilpas, un tā ir O(n^3). Štrasena algoritms reizina divas matricas O(n^2.8974) laikā.
• Kūlija–Tūkija ātrās Furjē transformācijas (FFT) algoritms ir visizplatītākais FFT algoritms. Tas ir dalīšanas un iekarošanas algoritms, kas darbojas O(N log N) laikā.
• Karatsuba algoritms ātrai reizināšanai veic divu bināro virkņu reizināšanu O(n^1.59) kur n ir binārās virknes garums.

Skaldi un valdi algoritma priekšrocības:

• Sarežģītu problēmu risināšana: Skaldi un valdi tehnika ir instruments sarežģītu problēmu konceptuālai risināšanai. piem. Hanojas torņa mīkla. Tas prasa veidu, kā sadalīt problēmu apakšproblēmās un atrisināt tās visas kā atsevišķus gadījumus un pēc tam apvienot apakšproblēmas ar sākotnējo problēmu.
• Algoritma efektivitāte: Skaldi un valdi algoritms bieži palīdz atklāt efektīvus algoritmus. Tā ir atslēga tādiem algoritmiem kā ātrā kārtošana un sapludināšanas kārtošana, kā arī ātras Furjē transformācijas.
• Paralēlisms: Parasti sadalīšanas un iekarošanas algoritmus izmanto vairāku procesoru iekārtās ar dalītas atmiņas sistēmām, kur datu komunikācija starp procesoriem nav jāplāno iepriekš, jo uz dažādiem procesoriem var tikt izpildītas atšķirīgas apakšproblēmas.
• Piekļuve atmiņai: Šie algoritmi, protams, efektīvi izmanto atmiņas kešatmiņas. Tā kā apakšproblēmas ir pietiekami mazas, lai tās atrisinātu kešatmiņā, neizmantojot galveno atmiņu, kas ir lēnāka. Jebkurš algoritms, kas efektīvi izmanto kešatmiņu, tiek saukts par aizmirsto kešatmiņu.

Skaldi un valdi algoritma trūkumi:

• Pieskaitāmās izmaksas: Problēmas sadalīšanas apakšproblēmās un pēc tam risinājumu apvienošanas process var prasīt papildu laiku un resursus. Šīs pieskaitāmās izmaksas var būt nozīmīgas problēmām, kas jau ir salīdzinoši nelielas vai kurām ir vienkāršs risinājums.
• Sarežģītība: Problēmas sadalīšana mazākās apakšproblēmās var palielināt kopējā risinājuma sarežģītību. Tas jo īpaši attiecas uz gadījumiem, kad apakšproblēmas ir savstarpēji atkarīgas un ir jāatrisina noteiktā secībā.
• Īstenošanas grūtības: Dažas problēmas ir grūti sadalīt mazākās apakšproblēmās vai arī tām ir nepieciešams sarežģīts algoritms. Šādos gadījumos var būt grūti īstenot 'skaldi un valdi' risinājumu.
• Atmiņas ierobežojumi: Strādājot ar lielām datu kopām, atmiņas prasības apakšproblēmu starprezultātu glabāšanai var kļūt par ierobežojošu faktoru.

Bieži uzdotie jautājumi (FAQ) par sadali un valdi algoritmu:

1. Kas ir sadali un valdi algoritms?

Sadaliet un iekarojiet ir problēmu risināšanas paņēmiens, kurā problēma tiek sadalīta mazākās, vieglāk pārvaldāmās apakšproblēmās. Šīs apakšproblēmas tiek atrisinātas rekursīvi, un pēc tam to risinājumi tiek apvienoti, lai atrisinātu sākotnējo problēmu.

2. Kādi ir galvenie soļi, kas ietverti sadalīšanas un iekarošanas algoritmā?

Galvenie soļi ir:

panda kūst

Sadaliet : sadaliet problēmu mazākās apakšproblēmās.

Iekarot : Atrisiniet apakšuzdevumus rekursīvi.

Apvienot : Apvienojiet vai apvienojiet apakšproblēmu risinājumus, lai iegūtu sākotnējās problēmas risinājumu.

3. Kādi ir daži problēmu piemēri, kas atrisinātas, izmantojot programmu “Skaldi un valdi”?

Sadaliet un iekarojiet algoritmu izmanto šķirošanas algoritmos, piemēram, sapludināšanas kārtošanā un ātrā kārtošanā, tuvākā punktu pāra atrašanā, Štrāsena algoritmā utt.

4. Kā sapludināšanas kārtošana izmanto pieeju sadali un iekaro?

Sapludināšanas kārtošana sadala masīvu divās daļās, rekursīvi kārto katru pusi un pēc tam sapludina sakārtotās puses, lai izveidotu galīgo sakārtoto masīvu.

java hello programma

5. Kāda ir sadalīšanas un iekarošanas algoritmu laika sarežģītība?

Laika sarežģītība atšķiras atkarībā no konkrētās problēmas un tā, kā tā tiek īstenota. Parasti daudziem sadalīšanas un iekarošanas algoritmiem laika sarežģītība ir O(n log n) vai labāka.

6. Vai sadalīt un iekarot algoritmus var paralēli?

Jā, sadalīšanas un iekarošanas algoritmi bieži vien ir dabiski paralēli, jo neatkarīgas apakšproblēmas var atrisināt vienlaikus. Tas padara tos piemērotus paralēlām skaitļošanas vidēm.

7. Kādas ir dažas stratēģijas bāzes gadījuma izvēlei sadalīšanas un iekarošanas algoritmos?

Bāzes gadījumam jābūt pietiekami vienkāršam, lai to atrisinātu tieši, bez tālākas sadalīšanas. To bieži izvēlas, pamatojoties uz mazāko ievades lielumu, kurā problēmu var atrisināt triviāli.

garš līdz stīgai

8. Vai ir kādi trūkumi vai ierobežojumi, izmantojot Divide and Conquer?

Lai gan “Skaldi un valdi” var radīt efektīvus risinājumus daudzām problēmām, tā var nebūt piemērota visiem problēmu veidiem. Rekursijas un risinājumu apvienošanas radītās pieskaitāmās izmaksas var radīt bažas arī ļoti lielu problēmu gadījumā.

9. Kā jūs analizējat sadalīšanas un iekarošanas algoritmu telpas sarežģītību?

Telpas sarežģītība ir atkarīga no tādiem faktoriem kā rekursijas dziļums un papildu telpa, kas nepieciešama risinājumu apvienošanai. Telpas sarežģītības analīze parasti ietver katra rekursīvā zvana izmantotās vietas apsvēršanu.

10. Kādas ir kopīgas algoritma “Skaldi un iekaro” priekšrocības?

Algoritmam sadali un iekaro ir daudz priekšrocību. Daži no tiem ietver:

• Sarežģītu problēmu risināšana
• Algoritma efektivitāte
• Paralēlisms
• Piekļuve atmiņai

Sadaliet un iekarojiet ir populāra algoritmu metode datorzinātnēs, kas ietver problēmas sadalīšanu mazākās apakšproblēmās, katras apakšproblēmas atrisināšanu atsevišķi un apakšproblēmu risinājumu apvienošanu, lai atrisinātu sākotnējo problēmu. Šīs metodes pamatideja ir sadalīt problēmu mazākās, vieglāk pārvaldāmās apakšproblēmās, kuras var vieglāk atrisināt.