Forskel mellem randomiseret og rekursiv algoritme

Randomized vs Recursive Algorithm

Randomiserede algoritmer indarbejder en følelse af tilfældighed i sin logik ved at foretage tilfældige valg under algoritmen. På grund af denne tilfældighed kan algoritmens adfærd ændre sig selv for en fast indgang. Til mange problemer giver randomiserede algoritmer de mest enkle 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 bruges i vid udstrækning til at finde løsninger på problemer inden for datalogi, og mange højt programmeringssprog understøtter rekursion.

Hvad er en randomiseret algoritme?

Randomiserede algoritmer indbefatter en følelse af tilfældighed ved at lave tilfældige valg, som styrer algoritmens udførelse. Dette gøres typisk ved at tage et sæt tilfældige tal genereret af en pseudorandom-nummergenerator som en ekstra indgang. På grund af dette kan algoritmens adfærd ændre sig selv for en fast indgang. Quicksort er en almindeligt kendt algoritme, der bruger begrebet tilfældighed og har en driftstid på O (n log n) uanset inputegenskaberne. Endvidere anvendes randomiseret trinvis byggemetode til bygningskonstruktioner som konveks skrog i beregningsgeometri. I denne metode permuteres inputpunkterne tilfældigt og indsættes derefter en efter en ind i strukturen. Implementering af en randomiseret algoritme er forholdsvis enkel end at implementere 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 samme problem. I en rekursiv algoritme defineres en funktion i forhold til den tidligere version af sig selv. Det er vigtigt at bemærke, at denne selvregistrering skal have en opsigelsesbetingelse for at undgå at henvise sig selv for evigt. Afslutningsbetingelsen kontrolleres, inden den refererer til sig selv. Det oprindelige trin i en rekursiv algoritme er relateret til basisklausulen i den rekursive definition af problemet. De trin, der følger det første trin, er relateret til problemets induktive klausuler. Rekursive algoritmer giver en enklere løsning i mange situationer, og det er tættere på den naturlige måde at tænke på end den iterative algoritme for det samme problem. Men generelt kræver rekursive algoritmer mere hukommelse, og de er beregningsdygtige.

Hvad er forskellen mellem en randomiseret og en rekursiv algoritme?

Tilfældige algoritmer er algoritmer, der bruger en følelse af tilfældighed ved at lave tilfældige valg, som kan påvirke algoritmens udførelse, 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 delproblemer med samme problem. På grund af tilfældigheden i tilfældige algoritmer kan algoritmens adfærd ændre sig selv for det samme input (i forskellige henrettelser af algoritmen). Men dette er ikke muligt i rekursive algoritmer, og opførelsen af ​​en rekursiv algoritme ville være den samme for en fast indgang.