Juhuslik vs rekursiivne algoritm
Juhuslikud algoritmid sisaldavad oma loogikasse juhuslikkuse tunnet, tehes algoritmi täitmise ajal juhuslikke valikuid. Selle juhuslikkuse tõttu võib algoritmi käitumine muutuda isegi fikseeritud sisendi korral. Paljude probleemide jaoks pakuvad juhuslikud algoritmid kõige lihtsamad ja tõhusamad lahendused. Rekursiivsed algoritmid põhinevad ideel, et probleemile saab lahenduse leida, leides lahendusi sama ülesande väiksematele alamülesannetele. Rekursiooni kasutatakse laialdaselt arvutiteaduse probleemidele lahenduste leidmiseks ja paljud kõrgetasemelised programmeerimiskeeled toetavad rekursiooni.
Mis on juhuslik algoritm?
Juhuslikud algoritmid sisaldavad juhuslikkuse tunnet, tehes juhuslikke valikuid, mis juhivad algoritmi täitmist. Tavaliselt tehakse seda pseudojuhuslike numbrite generaatori poolt genereeritud juhuslike arvude komplekti lisamise teel. Tänu sellele võib algoritmi käitumine muutuda isegi fikseeritud sisendi puhul. Quicksort on lai alt tuntud algoritm, mis kasutab juhuslikkuse kontseptsiooni ja mille tööaeg on O(n log n), sõltumata sisendomadustest. Lisaks kasutatakse arvutusgeomeetrias ehituskonstruktsioonide, nagu kumer kere, jaoks randomiseeritud inkrementaalset ehitusmeetodit. Selle meetodi puhul muudetakse sisendpunktid juhuslikult ja sisestatakse seejärel ükshaaval struktuuri. Randomiseeritud algoritmi rakendamine on suhteliselt lihtne kui sama probleemi jaoks deterministliku algoritmi rakendamine. Randomiseeritud algoritmi kavandamise suurim väljakutse seisneb aja ja ruumi keerukuse asümptootilise analüüsi tegemises.
Mis on rekursiivne algoritm?
Rekursiivsed algoritmid põhinevad ideel, et probleemile saab lahenduse leida, leides lahendusi sama ülesande väiksematele alamülesannetele. Rekursiivses algoritmis defineeritakse funktsioon enda varasema versiooni järgi. Oluline on märkida, et sellel enesele viitamisel peaks olema lõpetamise tingimus, et vältida enesele viitamist igavesti. Lõpetamistingimust kontrollitakse enne iseendale viitamist. Rekursiivse algoritmi algetapp on seotud ülesande rekursiivse definitsiooni alusklausliga. Algsele sammule järgnevad sammud on seotud probleemi induktiivklauslitega. Rekursiivsed algoritmid pakuvad paljudes olukordades lihtsamat lahendust ja on loomulikule mõtteviisile lähemal kui sama probleemi iteratiivne algoritm. Kuid üldiselt nõuavad rekursiivsed algoritmid rohkem mälu ja need on arvutuslikult kallid.
Mis vahe on juhuslikul ja rekursiivsel algoritmil?
Juhuslikud algoritmid on algoritmid, mis kasutavad juhuslikkuse tunnet, tehes juhuslikke valikuid, mis võivad mõjutada algoritmi täitmist, samas kui rekursiivsed algoritmid on algoritmid, mis põhinevad ideel, et probleemile saab lahenduse leida lahendused sama probleemi väiksematele alamprobleemidele. Juhuslike algoritmide juhuslikkuse tõttu võib algoritmi käitumine muutuda isegi sama sisendi korral (algoritmi erinevatel täitmistel). Kuid see pole rekursiivsete algoritmide puhul võimalik ja rekursiivse algoritmi käitumine oleks fikseeritud sisendi puhul sama.
