Ero satunnaistetun ja rekursiivisen algoritmin välillä

Satunnaistettu vs. rekursiivinen algoritmi

Satunnaistetut algoritmit sisällyttävät logiikkaansa satunnaisuuden tunteen tekemällä satunnaisia ​​valintoja algoritmin suorittamisen aikana. Tästä satunnaisuudesta johtuen algoritmin käyttäytyminen voi muuttua jopa kiinteälle tulolle. Moniin ongelmiin satunnaistetut algoritmit tarjoavat yksinkertaisimmat ja tehokkaimmat ratkaisut. Rekursiiviset algoritmit perustuvat ajatukseen, että ratkaisu ongelmaan voidaan löytää etsimällä ratkaisuja saman ongelman pienempiin alaongelmiin. Rekursiota käytetään laajalti ratkaisujen löytämiseen tietotekniikan ongelmiin, ja monet korkean tason ohjelmointikielet tukevat rekursiota.

Mikä on satunnaistettu algoritmi?

Satunnaistetut algoritmit sisältävät satunnaisuuden tunteen tekemällä satunnaisia ​​valintoja, jotka ohjaavat algoritmin suorittamista. Tämä tehdään tyypillisesti ottamalla lisäsyötteenä pseudo-satunnaislukugeneraattorin generoima satunnaisluku. Tästä johtuen algoritmin käyttäytyminen voi muuttua jopa kiinteälle tulolle. Quicksort on laajalti tunnettu algoritmi, joka käyttää sattumanvaraisuuden käsitettä ja sen juoksuaika on O (n log n) tulo-ominaisuuksista riippumatta. Lisäksi käytettiin satunnaistettua inkrementaalista rakennusmenetelmää rakenteisiin, kuten kupera runko, laskennallisessa geometriassa. Tässä menetelmässä syöttöpisteet peruutetaan satunnaisesti ja lisätään sitten yksi kerrallaan rakenteeseen. Satunnaistetun algoritmin toteuttaminen on suhteellisen yksinkertaista kuin deterministisen algoritmin toteuttaminen samaan ongelmaan. Suurin haaste satunnaistetun algoritmin suunnittelussa on asymptoottisen analyysin suorittaminen ajan ja tilan monimutkaisuudelle.

Mikä on rekursiivinen algoritmi?

Rekursiiviset algoritmit perustuvat ajatukseen, että ratkaisu ongelmaan voidaan löytää etsimällä ratkaisuja saman ongelman pienempiin alaongelmiin. Rekursiivisessa algoritmissa funktio määritetään sen aikaisemman version perusteella. On tärkeää huomata, että tällä itseviittauksella tulisi olla päättymisehto, jotta vältetään viittaaminen itseensä ikuisesti. Lopetusolosuhteet tarkistetaan ennen viittaamista itseensä. Rekursiivisen algoritmin ensimmäinen vaihe liittyy ongelman rekursiivisen määritelmän peruslausekkeeseen. Alkuvaihetta seuraavat vaiheet liittyvät ongelman induktiivisiin lauseisiin. Rekursiiviset algoritmit tarjoavat yksinkertaisemman ratkaisun monissa tilanteissa ja se on lähempänä luonnollista ajattelutapaa kuin saman ongelman iteratiivinen algoritmi. Mutta yleensä rekursiiviset algoritmit vaativat enemmän muistia ja ne ovat laskennallisesti kalliita.

Mikä on ero satunnaistetun ja rekursiivisen algoritmin välillä?

Satunnaiset algoritmit ovat algoritmeja, jotka käyttävät sattumanvaraisuutta tekemällä satunnaisia ​​valintoja, jotka voivat vaikuttaa algoritmin suorittamiseen, kun taas rekursiiviset algoritmit ovat algoritmeja, jotka perustuvat ajatukseen, että ratkaisu ongelmaan voidaan löytää etsimällä ratkaisuja pienempiin alaongelmiin samasta ongelmasta. Satunnaisten algoritmien satunnaisuuden takia algoritmin käyttäytyminen voi muuttua jopa samalla sisääntulolla (algoritmin erilaisissa suorituksissa). Mutta tämä ei ole mahdollista rekursiivisissa algoritmeissa ja rekursiivisen algoritmin käyttäytyminen olisi sama kiinteälle tulolle.