Satunnaistettu vs. rekursiivinen algoritmi
Satunnaistetut algoritmit sisällyttävät logiikkaan satunnaisuuden tunteen tekemällä satunnaisia valintoja algoritmin suorituksen aikana. Tästä satunnaisuudesta johtuen algoritmin käyttäytyminen voi muuttua myös kiinteässä syötteessä. Satunnaistetut algoritmit tarjoavat moniin ongelmiin 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 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ötöksi joukko satunnaislukuja, jotka on muodostanut näennäissatunnaislukugeneraattori. Tästä johtuen algoritmin käyttäytyminen voi muuttua jopa kiinteän syötteen kohdalla. Quicksort on laajalti tunnettu algoritmi, joka käyttää satunnaisuuskäsitettä ja jonka käyntiaika on O (n log n) tulo-ominaisuuksista riippumatta. Lisäksi satunnaistettua inkrementaalirakennemenetelmää käytetään rakennusrakenteiden, kuten kuperan rungon, laskemisgeometriassa. Tässä menetelmässä syöttökohdat muunnetaan satunnaisesti ja lisätään sitten yksi kerrallaan rakenteeseen. Satunnaistetun algoritmin toteuttaminen on suhteellisen yksinkertaista kuin deterministisen algoritmin toteuttaminen samalle ongelmalle. Suurin haaste satunnaistetun algoritmin suunnittelussa on asymptoottisen analyysin tekeminen 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ääritellään itsensä aikaisemman version perusteella. On tärkeää huomata, että tällä itseviittauksella tulisi olla irtisanomisehto, jotta vältetään itsensä viittaaminen ikuisesti. Irtisanomisen ehto tarkistetaan ennen itse viittaamista. Rekursiivisen algoritmin ensimmäinen vaihe liittyy ongelman rekursiivisen määrittelyn peruslauseeseen. Ensimmäisen vaiheen vaiheet liittyvät ongelman induktiivisiin lausekkeisiin. Rekursiiviset algoritmit tarjoavat yksinkertaisemman ratkaisun monissa tilanteissa ja ovat lähempänä luonnollista ajattelutapaa kuin saman ongelman iteratiivinen algoritmi. Mutta yleensärekursiiviset algoritmit vaativat enemmän muistia ja ne 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 toteuttamiseen, kun taas rekursiiviset algoritmit ovat algoritmeja, jotka perustuvat ajatukseen, että ongelman ratkaisu voidaan löytää etsimällä ratkaisuja pienempiin alaongelmiin saman ongelman. Satunnaisalgoritmien satunnaisuuden vuoksi algoritmin käyttäytyminen voi muuttua jopa samalle tulolle (algoritmin eri toteutuksissa). Mutta tämä ei ole mahdollista rekursiivisissa algoritmeissa ja rekursiivisen algoritmin käyttäytyminen olisi sama kiinteälle tulolle.
