Forskel mellem tilfældig og rekursiv algoritme

Randomiseret vs rekursiv algoritme

Tilfældige algoritmer indarbejder en følelse af tilfældighed i dens logik ved at foretage tilfældige valg under udførelsen af ​​algoritmen. På grund af denne tilfældighed kan opførslen af ​​algoritmen ændres, selv for et fast input. For mange problemer giver randomiserede algoritmer de mest enkleste og effektive løsninger. Rekursive algoritmer er baseret på ideen om, at løsningen på et problem kan findes ved at finde løsninger på mindre underproblemer med det samme problem. Rekursion er vidt brugt til at finde løsninger på computervidenskabsproblemer, og mange programmeringssprog på højt niveau understøtter rekursion.

Hvad er en tilfældig algoritme?

Tilfældige algoritmer indarbejder en følelse af tilfældighed ved at foretage tilfældige valg, der styrer udførelsen af ​​algoritmen. Dette gøres typisk ved at tage et sæt tilfældige tal genereret af en pseudorandom-nummergenerator som et ekstra input. På grund af dette kan algoritmens adfærd ændres, selv for et fast input. Quicksort er en bredt kendt algoritme, der bruger begrebet tilfældighed og har en køretid på O (n log n) uanset inputegenskaber. Desuden anvendes randomiseret inkrementel konstruktionsmetode til bygning af strukturer som konvekse skrog i beregningsgeometri. I denne metode permiteres indgangspunkterne tilfældigt og indsættes derefter en efter en i strukturen. Implementering af en randomiseret algoritme er relativt simpelt end implementering af en deterministisk algoritme til det samme problem. Den største udfordring ved at designe en randomiseret algoritme ligger i at udføre asymptotisk analyse for tid og rumkompleksitet.

Hvad er en rekursiv algoritme?

Rekursive algoritmer er baseret på ideen om, at løsningen på et problem kan findes ved at finde løsninger på mindre underproblemer med det samme problem. I en rekursiv algoritme defineres en funktion ud fra den tidligere version af sig selv. Det er vigtigt at bemærke, at denne selvhenvisning bør have en opsigelsesbetingelse for at undgå at referere sig selv for evigt. Afslutningsbetingelsen kontrolleres, før der refereres til sig selv. Det første trin i en rekursiv algoritme er relateret til basisbestemmelsen i den rekursive definition af problemet. Trinene, der følger det indledende trin, er relateret til de induktive klausuler om problemet. Rekursive algoritmer giver en enklere løsning i mange situationer, og det er tættere på den naturlige tankegang end den iterative algoritme for det samme problem. Men generelt kræver rekursive algoritmer mere hukommelse, og de er beregningsmæssigt dyre.

Hvad er forskellen mellem en tilfældig og en rekursiv algoritme?

Tilfældige algoritmer er algoritmer, der bruger en følelse af tilfældighed ved at foretage tilfældige valg, der kan påvirke udførelsen af ​​algoritmen, mens rekursive algoritmer er algoritmer, der er baseret på ideen om, at en løsning på et problem kan findes ved at finde løsninger på mindre underproblemer af det samme problem. På grund af tilfældigheden i de tilfældige algoritmer kunne algoritmenes adfærd ændres selv for det samme input (i forskellige udførelser af algoritmen). Men dette er ikke muligt i rekursive algoritmer, og opførslen af ​​en rekursiv algoritme ville være den samme for et fast input.