Erinevus juhusliku ja rekursiivse algoritmi vahel

Juhuslik vs rekursiivne algoritm

Juhuslikud algoritmid hõlmavad oma loogikas 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 korral pakuvad randomiseeritud algoritmid kõige lihtsamaid ja tõhusamaid lahendusi. Rekursiivsed algoritmid põhinevad ideel, et probleemile saab lahenduse leida lahendused sama probleemi väiksematele alamprobleemidele. Rekursiooni kasutatakse laialdaselt infotehnoloogia probleemidele lahenduste leidmiseks ja paljud kõrgetasemelised programmeerimiskeeled toetavad rekursiooni.

Mis on juhuslik algoritm?

Juhuslikud algoritmid hõlmavad juhuslikkuse tunnet, tehes juhuslikke valikuid, mis juhendavad algoritmi täitmist. Tavaliselt tehakse selleks pseudo-juhuslike arvude generaatori poolt genereeritud juhuslike arvude komplekt täiendava sisendina. Seetõttu võib algoritmi käitumine muutuda isegi fikseeritud sisendi korral. Quicksort on laialt tuntud algoritm, mis kasutab juhuslikkuse mõistet ja selle tööaeg on O (n log n) sõltumata sisendomadustest. Lisaks kasutatakse arvutusgeomeetrias selliste konstruktsioonide nagu kumera kere ehitamiseks juhuslikku lisanduvat ehitusmeetodit. Selle meetodi korral permuteeritakse sisendpunktid juhuslikult ja sisestatakse seejärel ükshaaval konstruktsiooni. Juhusliku algoritmi juurutamine on suhteliselt lihtne kui sama probleemi jaoks deterministliku algoritmi rakendamine. Randomiseeritud algoritmi kujundamisel on suurim väljakutse asümptootilise analüüsi teostamine aja ja ruumi keerukuse osas.

Mis on rekursiivne algoritm?

Rekursiivsed algoritmid põhinevad ideel, et probleemile saab lahenduse leida lahendused sama probleemi väiksematele alamprobleemidele. Rekursiivses algoritmis on funktsioon määratletud varasema versiooniga. Oluline on märkida, et sellel eneseviitamisel peaks olema lõpetamise tingimus, et vältida viitamist iseendale igavesti. Enne ise viitamist kontrollitakse lõpetamise tingimust. Rekursiivse algoritmi algne samm on seotud probleemi rekursiivse määratluse alusklausliga. Esialgsele etapile järgnevad sammud on seotud probleemi induktiivklauslitega. Rekursiivsed algoritmid pakuvad paljudes olukordades lihtsamat lahendust ja see on lähemal loomulikule mõtteviisile kui sama probleemi iteratiivne algoritm. Kuid üldiselt vajavad 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 võib leida lahenduse, leides lahendusi väiksematele alamprobleemidele sama probleem. 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 fikseeritud sisendi korral oleks sama.