Randomisert vs rekursiv algoritme
Randomiserte algoritmer inkorporerer en følelse av tilfeldighet i sin logikk ved å gjøre tilfeldige valg under utførelsen av algoritmen. På grunn av denne tilfeldigheten kan oppførselen til algoritmen endres selv for en fast inngang. For mange problemer gir randomiserte algoritmer de enkleste og mest effektive løsningene. Rekursive algoritmer er basert på ideen om at løsningen på et problem kan finnes ved å finne løsninger på mindre underproblemer av samme problem. Rekursjon er mye brukt for å finne løsninger på problemer innen informatikk, og mange programmeringsspråk på høyt nivå støtter rekursjon.
Hva er en randomisert algoritme?
Randomiserte algoritmer inkorporerer en følelse av tilfeldighet ved å gjøre tilfeldige valg som styrer utførelsen av algoritmen. Dette gjøres vanligvis ved å ta et sett med tilfeldige tall generert av en pseudorandom-tallgenerator som en ekstra inngang. På grunn av dette kan oppførselen til algoritmen endres selv for en fast inngang. Quicksort er en allment kjent algoritme som bruker begrepet tilfeldighet og den har en kjøretid på O(n log n) uavhengig av inngangsegenskapene. Videre brukes randomisert inkrementell konstruksjonsmetode for å bygge strukturer som konvekse skrog i beregningsgeometri. I denne metoden blir inngangspunktene tilfeldig permutert og deretter satt inn en etter en i strukturen. Å implementere en randomisert algoritme er relativt enkelt enn å implementere en deterministisk algoritme for samme problem. Den største utfordringen med å designe en randomisert algoritme ligger i å utføre asymptotisk analyse for tid og romkompleksitet.
Hva er en rekursiv algoritme?
Rekursive algoritmer er basert på ideen om at løsningen på et problem kan finnes ved å finne løsninger på mindre underproblemer av samme problem. I en rekursiv algoritme er en funksjon definert i form av den tidligere versjonen av seg selv. Det er viktig å merke seg at denne selvreferansen bør ha en oppsigelsesbetingelse for å unngå å referere seg selv for alltid. Oppsigelsesvilkåret kontrolleres før det refereres til seg selv. Det første trinnet i en rekursiv algoritme er relatert til basisklausulen i den rekursive definisjonen av problemet. Trinnene som følger det første trinnet er relatert til de induktive klausulene i problemet. Rekursive algoritmer gir en enklere løsning i mange situasjoner og den er nærmere den naturlige tenkemåten enn den iterative algoritmen for samme problem. Men generelt krever rekursive algoritmer mer minne, og de er beregningsmessig dyre.
Hva er forskjellen mellom en randomisert og en rekursiv algoritme?
Tilfeldige algoritmer er algoritmer som bruker en følelse av tilfeldighet ved å gjøre tilfeldige valg som kan påvirke utførelsen av algoritmen, mens rekursive algoritmer er algoritmer som er basert på ideen om at en løsning på et problem kan finnes ved å finne løsninger på mindre underproblemer av samme problem. På grunn av tilfeldigheten i de tilfeldige algoritmene, kan oppførselen til algoritmen endre seg selv for den samme inngangen (i forskjellige utførelser av algoritmen). Men dette er ikke mulig i rekursive algoritmer, og oppførselen til en rekursiv algoritme vil være den samme for en fast inngang.
