Randomized vs Rekursiewe Algoritme
Randomized algoritmes inkorporeer 'n gevoel van ewekansigheid in sy logika deur ewekansige keuses te maak tydens die uitvoering van die algoritme. As gevolg van hierdie willekeurigheid, kan die gedrag van die algoritme selfs vir 'n vaste inset verander. Vir baie probleme bied ewekansige algoritmes die eenvoudigste en doeltreffendste oplossings. Rekursiewe algoritmes is gebaseer op die idee dat die oplossing vir 'n probleem gevind kan word deur oplossings vir kleiner subprobleme van dieselfde probleem te vind. Rekursie word wyd gebruik om oplossings vir probleme in rekenaarwetenskap te vind en baie hoëvlak-programmeertale ondersteun rekursie.
Wat is 'n ewekansige algoritme?
Ewekansige algoritmes inkorporeer 'n gevoel van ewekansigheid deur ewekansige keuses te maak wat die uitvoering van die algoritme rig. Dit word tipies gedoen deur 'n stel ewekansige getalle wat deur 'n pseudorandomgetalgenerator gegenereer word as 'n bykomende inset te neem. As gevolg hiervan kan die gedrag van die algoritme selfs vir 'n vaste invoer verander. Quicksort is 'n wyd bekende algoritme wat die konsep van ewekansigheid gebruik en dit het 'n looptyd van O(n log n) ongeag die invoer eienskappe. Verder word gerandomiseerde inkrementele konstruksiemetode gebruik vir die bou van strukture soos konvekse romp in berekeningsgeometrie. In hierdie metode word die invoerpunte lukraak gepermuteer en dan een vir een in die struktuur ingevoeg. Die implementering van 'n gerandomiseerde algoritme is relatief eenvoudig as die implementering van 'n deterministiese algoritme vir dieselfde probleem. Die grootste uitdaging in die ontwerp van 'n ewekansige algoritme lê in die uitvoering van asimptotiese analise vir tyd en ruimte kompleksiteit.
Wat is 'n rekursiewe algoritme?
Rekursiewe algoritmes is gebaseer op die idee dat die oplossing vir 'n probleem gevind kan word deur oplossings vir kleiner subprobleme van dieselfde probleem te vind. In 'n rekursiewe algoritme word 'n funksie gedefinieer in terme van die vroeëre weergawe van homself. Dit is belangrik om daarop te let dat hierdie selfverwysing 'n beëindigingsvoorwaarde moet hê om te verhoed dat dit vir altyd self verwys word. Die beëindigingsvoorwaarde word nagegaan voordat daar na homself verwys word. Die aanvanklike stap van 'n rekursiewe algoritme hou verband met die basisklousule van die rekursiewe definisie van die probleem. Die stappe wat op die aanvanklike stap volg, hou verband met die induktiewe klousules van die probleem. Rekursiewe algoritmes bied 'n eenvoudiger oplossing in baie situasies en dit is nader aan die natuurlike manier van dink as die iteratiewe algoritme vir dieselfde probleem. Maar oor die algemeen vereis rekursiewe algoritmes meer geheue en dit is berekeningsduur.
Wat is die verskil tussen 'n gerandomiseerde en 'n rekursiewe algoritme?
Ewekansige algoritmes is algoritmes wat 'n gevoel van ewekansigheid gebruik deur ewekansige keuses te maak wat die uitvoering van die algoritme kan beïnvloed, terwyl rekursiewe algoritmes algoritmes is wat gebaseer is op die idee dat 'n oplossing vir 'n probleem gevind kan word deur te vind oplossings vir kleiner subprobleme van dieselfde probleem. As gevolg van die ewekansigheid in die ewekansige algoritmes, kan die gedrag van die algoritme selfs vir dieselfde insette verander (in verskillende uitvoerings van die algoritme). Maar dit is nie moontlik in rekursiewe algoritmes nie en die gedrag van 'n rekursiewe algoritme sal dieselfde wees vir 'n vaste invoer.
