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 opførsel ændre sig selv for et fast input. I 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 programmeringssprog på højt niveau understøtter rekursion.
Hvad er en randomiseret algoritme?
Randomiserede algoritmer indeholder 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 en ekstra input. På grund af dette kan algoritmens opførsel ændre sig selv for et fast input. Quicksort er en almindeligt kendt algoritme, der bruger begrebet tilfældighed, og den har en kørselstid på O (n log n) uanset inputegenskaberne. Yderligere anvendes randomiseret inkrementel konstruktionsmetode til bygningskonstruktioner som konveks skrog i beregningsgeometri. I denne metode permitteres inputpunkterne tilfældigt og indsættes derefter en efter en i strukturen. Implementering af en randomiseret algoritme er relativt enkel end implementering af en deterministisk algoritme for det samme problem. Den største udfordring i designet af 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 med det samme problem. I en rekursiv algoritme defineres en funktion i form af den tidligere version af sig selv. Det er vigtigt at bemærke, at denne selvhenvisning skal have en afslutningstilstand for at undgå at henvise til sig selv for evigt. Opsigelsesbetingelsen kontrolleres, før der henvises til sig selv. Det første trin i en rekursiv algoritme er relateret til grundparagrafen i den rekursive definition af problemet. De trin, der følger det indledende 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 genereltrekursive algoritmer kræver 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 det samme problem. På grund af tilfældigheden i de tilfældige algoritmer kan algoritmens opførsel ændre sig selv for det samme input (i forskellige udførelser af algoritmen). Men dette er ikke muligt i rekursive algoritmer, og en rekursiv algoritmes opførsel ville være den samme for et fast input.
