Randomiseret vs rekursiv algoritme
Randomiserede algoritmer inkorporerer en følelse af tilfældighed i sin logik ved at foretage tilfældige valg under udførelsen af algoritmen. På grund af denne tilfældighed kan algoritmens adfærd ændre sig selv for et fast input. 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 af samme problem. Rekursion er meget brugt til at finde løsninger på problemer inden for datalogi, og mange programmeringssprog på højt niveau understøtter rekursion.
Hvad er en randomiseret algoritme?
Randomiserede algoritmer inkorporerer 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-talgenerator som et ekstra input. På grund af dette kan adfærden af algoritmen ændre sig selv for et fast input. Quicksort er en almindeligt kendt algoritme, der bruger begrebet tilfældighed, og den har en køretid på O(n log n) uanset inputegenskaberne. Yderligere bruges randomiseret inkrementel konstruktionsmetode til at bygge strukturer som konvekse skrog i beregningsgeometri. I denne metode permuteres inputpunkterne tilfældigt og indsættes derefter et efter et i strukturen. Implementering af en randomiseret algoritme er relativt simpel end at implementere en deterministisk algoritme for det samme problem. Den største udfordring ved at designe en randomiseret algoritme ligger i at udføre asymptotisk analyse for tid og rum kompleksitet.
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 af samme problem. I en rekursiv algoritme er en funktion defineret 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. Opsigelsesbetingelsen kontrolleres, før der refereres til sig selv. Det indledende trin i en rekursiv algoritme er relateret til basisklausulen i den rekursive definition af problemet. Trinene, der følger det indledende trin, er relateret til de induktive klausuler i problemet. Rekursive algoritmer giver en enklere løsning i mange situationer, og den er tættere på den naturlige måde at tænke på end den iterative algoritme for samme problem. Men generelt kræver rekursive algoritmer mere hukommelse, og de er beregningsmæssigt dyre.
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 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 samme problem. På grund af tilfældigheden i de tilfældige algoritmer kan algoritmens adfærd ændre sig selv for det samme input (i forskellige udførelser af algoritmen). Men dette er ikke muligt i rekursive algoritmer, og adfærden af en rekursiv algoritme ville være den samme for et fast input.
