Satunnaistettu vs rekursiivinen algoritmi
Satunnaistettujen algoritmien logiikka sisältää satunnaisuuden tunteen tekemällä satunnaisia valintoja algoritmin suorittamisen aikana. Tästä satunnaisuudesta johtuen algoritmin käyttäytyminen voi muuttua jopa kiinteällä syötteellä. 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 osatehtäviin. Rekursiota käytetään laajasti ratkaisujen löytämiseen tietojenkäsittelytieteen 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ötteeksi joukko näennäissatunnaislukugeneraattorin generoimia satunnaislukuja. Tästä johtuen algoritmin käyttäytyminen voi muuttua jopa kiinteällä syötteellä. Quicksort on laaj alti tunnettu algoritmi, joka käyttää satunnaisuuden käsitettä ja sen ajoaika on O(n log n) syöteominaisuuksista riippumatta. Lisäksi satunnaistettua inkrementaalista rakennusmenetelmää käytetään rakennusrakenteissa, kuten kuperassa rungossa laskentageometriassa. Tässä menetelmässä syöttöpisteet permutoidaan satunnaisesti ja lisätään sitten yksitellen rakenteeseen. Satunnaistetun algoritmin toteuttaminen on suhteellisen yksinkertaista kuin deterministisen algoritmin toteuttaminen samalle ongelmalle. Suurin haaste satunnaistetun algoritmin suunnittelussa on ajan ja tilan monimutkaisuuden asymptoottisen analyysin suorittaminen.
Mikä on rekursiivinen algoritmi?
Rekursiiviset algoritmit perustuvat ajatukseen, että ratkaisu ongelmaan voidaan löytää etsimällä ratkaisuja saman ongelman pienempiin osatehtäviin. Rekursiivisessa algoritmissa funktio määritellään itsensä aikaisemman version perusteella. On tärkeää huomata, että tällä itseviittauksella tulee olla lopetusehto, jotta vältytään viittaamasta itseensä ikuisesti. Päättymisehto tarkistetaan ennen kuin viitataan itseensä. Rekursiivisen algoritmin alkuvaihe liittyy ongelman rekursiivisen määritelmän peruslauseeseen. Alkuvaihetta seuraavat vaiheet liittyvät ongelman induktiivisiin lauseisiin. Rekursiiviset algoritmit tarjoavat monissa tilanteissa yksinkertaisemman ratkaisun ja se on lähempänä luonnollista ajattelutapaa kuin saman ongelman iteratiivinen algoritmi. Mutta yleensä rekursiiviset algoritmit vaativat enemmän muistia ja ovat laskennallisesti kalliita.
Mitä eroa on satunnaistetulla ja rekursiivisella algoritmilla?
Satunnaisalgoritmit ovat algoritmeja, jotka käyttävät satunnaisuuden tunnetta 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 saman ongelman pienempiin osaongelmiin. Satunnaisalgoritmien satunnaisuudesta johtuen algoritmin käyttäytyminen voi muuttua jopa samalla syötteellä (algoritmin eri suorituksissa). Mutta tämä ei ole mahdollista rekursiivisissa algoritmeissa, ja rekursiivisen algoritmin käyttäytyminen olisi sama kiinteällä syötteellä.
