hajota ja hallitse Algoritmi on ongelmanratkaisutekniikka, jota käytetään ongelmien ratkaisemiseen jakamalla pääongelma osaongelmiin, ratkaisemalla ne yksitellen ja yhdistämällä ne sitten ratkaisun löytämiseksi alkuperäiseen ongelmaan. Tässä artikkelissa aiomme keskustella siitä, kuinka Divide and Conquer -algoritmi on hyödyllinen ja kuinka voimme käyttää sitä ongelmien ratkaisemiseen.

Sisällysluettelo

• Jaa ja hallitse -algoritmin määritelmä
• hajota ja hallitse -algoritmin toiminta
• Jaa ja hallitse -algoritmin ominaisuudet
• Esimerkkejä hajota ja hallitse -algoritmista
• hajota ja hallitse -algoritmin monimutkaisuusanalyysi
• Divide and Conquer -algoritmin sovellukset
• Jaa ja hallitse -algoritmin edut
• Jaa ja hallitse -algoritmin haitat

hajota ja hallitse Algoritmin määritelmä:

hajota ja hallitse -algoritmi sisältää suuremman ongelman jakamisen pienempiin osaongelmiin, niiden ratkaisemisen itsenäisesti ja niiden ratkaisujen yhdistämisen alkuperäisen ongelman ratkaisemiseksi. Perusideana on jakaa ongelma rekursiivisesti pienempiin osaongelmiin, kunnes niistä tulee riittävän yksinkertaisia ​​suoraan ratkaistaviksi. Kun osaongelmien ratkaisut on saatu, ne yhdistetään kokonaisratkaisun tuottamiseksi.

hajota ja hallitse -algoritmin toiminta:

Divide and Conquer -algoritmi voidaan jakaa kolmeen vaiheeseen: Jakaa , Valloittaa ja Yhdistää .

bfs ja dfs

1. Jaa:

• Pura alkuperäinen ongelma pienempiin osaongelmiin.
• Jokaisen osaongelman tulee edustaa osa kokonaisongelmaa.
• Tavoitteena on jakaa ongelma, kunnes se ei enää ole mahdollista.

2. Valloita:

• Ratkaise jokainen pienempi osaongelma erikseen.
• Jos aliongelma on tarpeeksi pieni (kutsutaan usein perustapaukseksi), ratkaisemme sen suoraan ilman lisärekursioita.
• Tavoitteena on löytää ratkaisuja näihin osaongelmiin itsenäisesti.

3. Yhdistä:

• Yhdistä aliongelmat saadaksesi lopullisen ratkaisun koko ongelmaan.
• Kun pienemmät osaongelmat on ratkaistu, yhdistämme niiden ratkaisut rekursiivisesti saadaksemme ratkaisun suurempaan ongelmaan.
• Tavoitteena on muotoilla ratkaisu alkuperäiseen ongelmaan yhdistämällä osaongelmien tulokset.

Jaa ja hallitse -algoritmin ominaisuudet:

Divide and Conquer -algoritmi sisältää ongelman jakamisen pienempiin, paremmin hallittaviin osiin, kunkin osan ratkaisemisen erikseen ja sitten ratkaisujen yhdistämisen alkuperäisen ongelman ratkaisemiseksi. Divide and Conquer -algoritmin ominaisuudet ovat:

• Ongelman jakaminen : Ensimmäinen askel on jakaa ongelma pienempiin, paremmin hallittaviin osaongelmiin. Tämä jako voidaan tehdä rekursiivisesti, kunnes aliongelmat ovat riittävän yksinkertaisia ​​ratkaistaviksi suoraan.
• Aliongelmien riippumattomuus : Jokaisen osaongelman tulee olla riippumaton muista, mikä tarkoittaa, että yhden osaongelman ratkaiseminen ei riipu toisen ratkaisusta. Tämä mahdollistaa aliongelmien rinnakkaiskäsittelyn tai samanaikaisen suorittamisen, mikä voi johtaa tehokkuuden lisääntymiseen.
• Jokaisen aliongelman voittaminen : Kun osaongelmat on jaettu, ne ratkaistaan ​​yksitellen. Tämä voi sisältää saman hajoa ja hallitse -lähestymistavan soveltamisen rekursiivisesti, kunnes aliongelmat ovat riittävän yksinkertaisia ​​ratkaistaviksi suoraan, tai siihen voi liittyä erilaisen algoritmin tai tekniikan soveltaminen.
• Ratkaisujen yhdistäminen : Aliongelmien ratkaisemisen jälkeen niiden ratkaisut yhdistetään, jotta saadaan ratkaisu alkuperäiseen ongelmaan. Tämän yhdistämisvaiheen tulee olla suhteellisen tehokas ja suoraviivainen, koska osaongelmien ratkaisut tulee suunnitella sopimaan yhteen saumattomasti.

Esimerkkejä hajota ja hallitse -algoritmista:

1. Maksimielementin löytäminen taulukosta:

Voimme käyttää Divide and Conquer -algoritmia löytääksemme taulukon maksimielementin jakamalla taulukon kahteen samankokoiseen alitaulukkoon, ja löydämme näistä kahdesta yksittäisestä puolikkaasta suurimman jakamalla ne jälleen kahteen pienempään puolikkaaseen. Tätä tehdään, kunnes saavutamme alitaulukot, joiden koko on 1. Kun elementit on saavutettu, palautetaan maksimielementti ja yhdistetään aliryhmät palauttamalla kunkin alitaulukon maksimi.

// 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>hei) palauta INT_MIN;  // Jos alitaulukossa on vain yksi elementti, palauta //-elementti if (lo == hi) return a[lo];  int mid = (lo + hi) / 2;  // Hae maksimielementti vasemmasta puoliskosta int leftMax = findMax(a, lo, mid);  // Hanki maksimielementti oikeasta puoliskosta int rightMax = findMax(a, mid + 1, hi);  // Palauttaa maksimielementin vasemmalta ja oikealta // 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) palauttaa Kokonaisluku.MIN_ARVO;  // Jos alitaulukossa on vain yksi elementti, palauta //-elementti if (lo == hi) return a[lo];  int mid = (lo + hi) / 2;  // Hae maksimielementti vasemmasta puoliskosta int leftMax = findMax(a, lo, mid);  // Hanki maksimielementti oikeasta puoliskosta int rightMax = findMax(a, mid + 1, hi);  // Palauttaa maksimielementin vasemmalta ja // oikealta puoliväliltä paluu 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') # Jos aliryhmässä on vain yksi elementti, palauta #-elementti, jos lo == hi: return a[lo] mid = (lo + hi) // 2 # Hanki maksimi elementti vasemmalta puoliskosta left_max = find_max(a, lo, mid) # Hae maksimielementti oikealta puoliskolta right_max = find_max(a, mid + 1, hi) # Palauta maksimielementti vasemmalta ja oikealta # 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;  // Jos alitaulukossa on vain yksi elementti, palauta //-elementti if (lo == hi) return a[lo];  int mid = (lo + hi) / 2;  // Hae maksimielementti vasemmasta puoliskosta int leftMax = FindMax(a, lo, mid);  // Hanki maksimielementti oikealta puolikkaalta int rightMax = FindMax(a, mid + 1, hi);  // Palauttaa maksimielementin vasemmalta ja // oikealta puoliväliltä paluu 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) palauttaa Number.MIN_ARVO;  // Jos alitaulukossa on vain yksi elementti, palauta //-elementti if (lo === hi) return a[lo];  const mid = Math.floor((lo + hi) / 2);  // Hae maksimielementti vasemmasta puoliskosta const leftMax = findMax(a, lo, mid);  // Hanki maksimielementti oikeasta puoliskosta const rightMax = findMax(a, mid + 1, hi);  // Palauttaa maksimielementin vasemmalta ja oikealta // half return Math.max(leftMax, rightMax); }>

2. Minimielementin löytäminen taulukosta:

Samoin voimme käyttää Divide and Conquer -algoritmia löytääksemme taulukon minimielementin jakamalla taulukon kahteen samankokoiseen alitaulukkoon ja etsimällä näiden kahden yksittäisen puolikkaan minimin jakamalla ne jälleen kahteen pienempään puolikkaaseen. Tätä tehdään, kunnes saavutamme alitaulukot, joiden koko on 1. Kun elementit on saavutettu, palautamme minimielementin ja yhdistämme alitaulukot palauttamalla kunkin alitaulukon minimin.

kuinka suuri näyttöni on

3. Yhdistä lajittelu:

Voimme käyttää Divide and Conquer -algoritmia lajitellaksesi taulukon nousevaan tai laskevaan järjestykseen jakamalla taulukon pienempiin aliryhmiin, lajittelemalla pienemmät alitaulukot ja yhdistämällä lajitellut taulukot alkuperäisen taulukon lajittelemiseksi.

hajota ja hallitse -algoritmin monimutkaisuusanalyysi:

T(n) = aT(n/b) + f(n), missä n = syötteen koko a = aliongelmien lukumäärä rekursiossa n/b = kunkin osatehtävän koko. Kaikkien aliongelmien oletetaan olevan samankokoisia. f(n) = rekursiivisen puhelun ulkopuolella tehdyn työn hinta, joka sisältää ongelman jakamisen ja ratkaisujen yhdistämiskustannukset

Jaa ja hallitse -algoritmin sovellukset:

Seuraavassa on joitain vakioalgoritmeja, jotka noudattavat Divide and Conquer -algoritmia:

• Quicksort on lajittelualgoritmi, joka poimii pivot-elementin ja järjestää taulukon elementit uudelleen siten, että kaikki valittua pivot-elementtiä pienemmät elementit siirtyvät pivotin vasemmalle puolelle ja kaikki suuremmat elementit siirtyvät oikealle puolelle. Lopuksi algoritmi lajittelee rekursiivisesti pivot-elementin vasemmalla ja oikealla puolella olevat aliryhmät.
• Yhdistä lajittelu on myös lajittelualgoritmi. Algoritmi jakaa taulukon kahteen puolikkaaseen, lajittelee ne rekursiivisesti ja lopuksi yhdistää kaksi lajiteltua puoliskoa.
• Lähin pistepari Ongelmana on löytää lähin pistepari pistejoukosta x-y tasossa. Ongelma voidaan ratkaista O(n^2) ajassa laskemalla jokaisen pisteparin etäisyydet ja vertaamalla etäisyyksiä minimiin. Divide and Conquer -algoritmi ratkaisee ongelman O(N log N) ajassa.
• Strassenin algoritmi on tehokas algoritmi kahden matriisin kertomiseen. Yksinkertainen menetelmä kahden matriisin kertomiseksi vaatii 3 sisäkkäistä silmukkaa ja on O(n^3). Strassenin algoritmi kertoo kaksi matriisia O(n^2.8974) ajassa.
• Cooley–Tukey Fast Fourier Transform (FFT) -algoritmi on FFT:n yleisin algoritmi. Se on jakaa ja hallitse -algoritmi, joka toimii O(N log N) ajassa.
• Karatsuba-algoritmi nopeaan kertolaskuun tekee kahden binäärimerkkijonon kertomisen O(n^1.59) jossa n on binäärimerkkijonon pituus.

Jaa ja hallitse -algoritmin edut:

• Vaikeiden ongelmien ratkaiseminen: Hajota ja hallitse -tekniikka on työkalu vaikeiden ongelmien käsitteelliseen ratkaisemiseen. esim. Hanoin torni palapeli. Se vaatii tapaa jakaa ongelma osaongelmiksi ja ratkaista ne kaikki yksittäistapauksina ja sitten yhdistää osaongelmat alkuperäiseen ongelmaan.
• Algoritmin tehokkuus: Jaa ja hallitse -algoritmi auttaa usein löytämään tehokkaita algoritmeja. Se on avain algoritmeihin, kuten Quick Sort ja Merge Sort, ja nopeisiin Fourier-muunnoksiin.
• Rinnakkaisuus: Normaalisti Divide and Conquer -algoritmeja käytetään moniprosessorikoneissa, joissa on jaetut muistijärjestelmät, joissa prosessorien välistä tiedonsiirtoa ei tarvitse suunnitella etukäteen, koska eri prosessoreissa voidaan suorittaa erillisiä osa-ongelmia.
• Muistin käyttö: Nämä algoritmit luonnollisesti hyödyntävät tehokkaasti muistivälimuistia. Koska aliongelmat ovat tarpeeksi pieniä, jotta ne voidaan ratkaista välimuistissa käyttämättä päämuistia, joka on hitaampi. Mitä tahansa algoritmia, joka käyttää välimuistia tehokkaasti, kutsutaan välimuistin huomaamattomaksi.

Jaa ja hallitse -algoritmin haitat:

• Yleiskustannukset: Ongelman jakaminen osaongelmiin ja sitten ratkaisujen yhdistäminen voi vaatia lisäaikaa ja resursseja. Tämä yleiskustannukset voivat olla merkittäviä ongelmissa, jotka ovat jo suhteellisen pieniä tai joihin on yksinkertainen ratkaisu.
• Monimutkaisuus: Ongelman jakaminen pienempiin osaongelmiin voi monimutkaistaa kokonaisratkaisua. Tämä pätee erityisesti silloin, kun osaongelmat ovat toisistaan ​​riippuvaisia ​​ja ne on ratkaistava tietyssä järjestyksessä.
• Toteutuksen vaikeus: Joitakin ongelmia on vaikea jakaa pienempiin osaongelmiin tai ne vaativat monimutkaisen algoritmin. Näissä tapauksissa hajota ja hallitse -ratkaisun toteuttaminen voi olla haastavaa.
• Muistin rajoitukset: Suurten tietojoukkojen kanssa työskenneltäessä muistivaatimukset aliongelmien välitulosten tallentamiseen voivat muodostua rajoittavaksi tekijäksi.

Usein kysytyt kysymykset (FAQ) hajota ja hallitse -algoritmista:

1. Mikä on Divide and Conquer -algoritmi?

Divide and Conquer on ongelmanratkaisutekniikka, jossa ongelma jaetaan pienempiin, paremmin hallittaviin osaongelmiin. Nämä osaongelmat ratkaistaan ​​rekursiivisesti, ja sitten niiden ratkaisut yhdistetään alkuperäisen ongelman ratkaisemiseksi.

2. Mitkä ovat Divide and Conquer -algoritmin tärkeimmät vaiheet?

Päävaiheet ovat:

keskimmäinen css-painike

Jakaa : Jaa ongelma pienempiin osaongelmiin.

Valloittaa : Ratkaise alitehtävät rekursiivisesti.

Yhdistää : Yhdistä tai yhdistä aliongelmien ratkaisut saadaksesi ratkaisun alkuperäiseen ongelmaan.

3. Mitä esimerkkejä ongelmista, jotka on ratkaistu Divide and Conquer -toiminnolla?

Divide and Conquer -algoritmia käytetään lajittelualgoritmeissa, kuten yhdistämislajittelussa ja pikalajittelussa, lähimmän pisteparin löytämisessä, Strassenin algoritmissa jne.

4. Kuinka yhdistämislajittelu käyttää Divide and Conquer -lähestymistapaa?

Yhdistämislajittelu jakaa taulukon kahteen puolikkaaseen, lajittelee rekursiivisesti kummankin puolikkaan ja yhdistää sitten lajitellut puolikkaat lopullisen lajiteltuun taulukkoon.

Madhubala

5. Mikä on Divide and Conquer -algoritmien aikamonimutkaisuus?

Aika monimutkaisuus vaihtelee tietyn ongelman ja sen toteutustavan mukaan. Yleensä monien Divide and Conquer -algoritmien aikamonimutkaisuus on O(n log n) tai parempi.

6. Voidaanko Divide and Conquer -algoritmeja rinnastaa?

Kyllä, Divide and Conquer -algoritmit ovat usein luonnollisesti rinnastettavissa, koska itsenäiset osaongelmat voidaan ratkaista samanaikaisesti. Tämä tekee niistä sopivia rinnakkaisiin laskentaympäristöihin.

7. Mitä strategioita on perustapauksen valitsemiseksi Divide and Conquer -algoritmeissa?

Perustapauksen tulee olla riittävän yksinkertainen, jotta se voidaan ratkaista suoraan ilman lisäjakoa. Se valitaan usein pienimmän syöttökoon perusteella, jossa ongelma voidaan ratkaista triviaalisti.

java luettelo

8. Onko Divide and Conquerin käytössä haittoja tai rajoituksia?

Vaikka Divide and Conquer voi johtaa tehokkaisiin ratkaisuihin moniin ongelmiin, se ei välttämättä sovellu kaikille ongelmatyypeille. Rekursiosta ja ratkaisujen yhdistämisestä aiheutuvat lisäkustannukset voivat olla huolestuttavia myös erittäin suurissa ongelmakokoissa.

9. Kuinka analysoit Divide and Conquer -algoritmien tilan monimutkaisuutta?

Tilan monimutkaisuus riippuu tekijöistä, kuten rekursiosta ja ratkaisujen yhdistämiseen tarvittavasta aputilasta. Avaruuden monimutkaisuuden analysointiin kuuluu tyypillisesti kunkin rekursiivisen kutsun käyttämän tilan huomioon ottaminen.

10. Mitkä ovat hajota ja hallitse -algoritmin yleiset edut?

Divide and Conquer -algoritmilla on lukuisia etuja. Jotkut niistä sisältävät:

• Vaikeiden ongelmien ratkaiseminen
• Algoritmin tehokkuus
• Rinnakkaisuus
• Muistin käyttö

Divide and Conquer on tietojenkäsittelytieteen suosittu algoritmitekniikka, jossa ongelma jaetaan pienempiin osaongelmiin, ratkaistaan ​​jokainen osaongelma itsenäisesti ja yhdistetään sitten ratkaisut osaongelmiin alkuperäisen ongelman ratkaisemiseksi. Tämän tekniikan perusideana on jakaa ongelma pienempiin, paremmin hallittaviin osaongelmiin, jotka voidaan ratkaista helpommin.