Forskjellen mellom randomisert og rekursiv algoritme

Randomized vs Recursive Algorithm

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 algoritmens oppførsel endres selv for et fast inngang. For mange problemer gir randomiserte algoritmer de mest enkle og 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 med det samme problemet. Rekursjon er mye brukt til å finne løsninger på problemer i datavitenskap og mange høyt programmeringsspråder støtter rekursjon.

Hva er en randomisert algoritme?

Randomiserte algoritmer inkorporerer en følelse av tilfeldighet ved å lage tilfeldige valg som styrer utførelsen av algoritmen. Dette gjøres vanligvis ved å ta et sett av tilfeldige tall som genereres av en pseudorandom-tall generator som en ekstra inngang. På grunn av dette kan algoritmens oppførsel endres selv for et 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 byggekonstruksjoner som konveks skrog i beregningsgeometri. I denne metoden blir inngangspunktene tilfeldig og deretter satt inn en etter en inn i strukturen. Implementering av en randomisert algoritme er relativt enkel enn å implementere en deterministisk algoritme for det samme problemet. Den største utfordringen ved å 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 med det samme problemet. 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 oppsigelsestilstand for å unngå å referere til seg selv for alltid. Oppsigelsestilstanden er sjekket før den refererer til seg selv. Det første trinnet i en rekursiv algoritme er relatert til grunnklausulen i den rekursive definisjonen av problemet. Trinnene som følger opprinnelsestrinnet er relatert til problemets induktive klausuler. Rekursive algoritmer gir en enklere løsning i mange situasjoner, og den er nærmere den naturlige tenkemåten enn den iterative algoritmen for det samme problemet. Men generelt krever rekursive algoritmer mer minne, og de er beregnende dyrt.

Hva er forskjellen mellom en randomisert og en rekursiv algoritme?

Tilfeldige algoritmer er algoritmer som bruker en følelse av tilfeldighet ved å lage tilfeldige valg som kan påvirke algoritmenes utførelse, 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 delproblemer av det samme problemet. På grunn av tilfeldigheten i tilfeldige algoritmer, kan algoritmens oppførsel endre seg selv for samme inngang (i forskjellige henrettelser 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.