Randomized vs Recursive Algorithm
Randomiserte algoritmer innlemmer en følelse av tilfeldighet i logikken ved å ta tilfeldige valg under utførelsen av algoritmen. På grunn av denne tilfeldigheten kan algoritmens oppførsel 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 bli funnet ved å finne løsninger på mindre delproblemer av samme problem. Rekursjon brukes mye 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 har en følelse av tilfeldighet ved å ta tilfeldige valg som styrer gjennomføringen 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 algoritmens oppførsel endres selv for en fast inngang. Quicksort er en allment kjent algoritme som bruker begrepet tilfeldighet og har en kjøretid på O (n log n) uavhengig av inngangsegenskapene. Videre brukes randomisert inkrementell konstruksjonsmetode for å bygge strukturer som konveks skrog i beregningsgeometri. I denne metoden blir inngangspunktene tilfeldig permuert og deretter satt inn en etter en i strukturen. Å implementere en randomisert algoritme er relativt enkelt enn å implementere en deterministisk algoritme for det samme problemet. 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 bli funnet ved å finne løsninger på mindre delproblemer av samme problem. I en rekursiv algoritme defineres en funksjon i forhold til den tidligere versjonen av seg selv. Det er viktig å merke seg at denne selvreferansen skal ha en avslutningstilstand for å unngå å referere seg for alltid. Oppsigelsestilstanden blir sjekket før den refererer 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 leddene i problemet. Rekursive algoritmer gir en enklere løsning i mange situasjoner, og det er nærmere den naturlige tankegangen enn den iterative algoritmen for det samme problemet. Men generelt,rekursive algoritmer krever mer minne, og de er beregningsdyr.
Hva er forskjellen mellom en randomisert og en rekursiv algoritme?
Tilfeldige algoritmer er algoritmer som bruker en følelse av tilfeldighet ved å ta 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 bli funnet ved å finne løsninger på mindre underproblemer av det samme problemet. På grunn av tilfeldigheten i de tilfeldige algoritmene, kan oppførselen til algoritmen endres selv for samme inngang (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.
