Skillnaden mellan Randomized och Recursive Algorithm

Randomized vs Recursive Algorithm

Randomiserade algoritmer införlivar en känsla av slumpmässighet i sin logik genom att göra slumpmässiga val under algoritmens utförande. På grund av denna slumpmässighet kan algoritmens beteende ändras även för en fast ingång. För många problem ger randomiserade algoritmer de enklaste och mest effektiva lösningarna. Rekursiva algoritmer bygger på tanken att lösningen på ett problem kan hittas genom att hitta lösningar på mindre delproblem av samma problem. Rekursion används ofta för att hitta lösningar på problem inom datavetenskap och många högkvalitativa programmeringsspråk stöder rekursion.

Vad är en randomiserad algoritm?

Randomiserade algoritmer innehåller en känsla av slumpmässighet genom att göra slumpmässiga val som styr utförandet av algoritmen. Detta görs vanligen genom att ta en uppsättning slumptal som genereras av en pseudorandom-talgenerator som en extra ingång. På grund av detta kan algoritmens beteende ändras även för en fast ingång. Quicksort är en allmänt känd algoritm som använder begreppet slumpmässighet och har en speltid på O (n log n) oavsett ingående egenskaper. Vidare används en randomiserad inkrementell byggnadsmetod för byggnadsstrukturer som konvex skrov i beräkningsgeometri. I denna metod permuteras inmatningspunkterna slumpmässigt och läggs sedan in en efter en in i strukturen. Genomförandet av en randomiserad algoritm är relativt enkel än att implementera en deterministisk algoritm för samma problem. Den största utmaningen vid utformningen av en randomiserad algoritm ligger i att utföra asymptotisk analys för tid och rymdkomplexitet.

Vad är en rekursiv algoritm?

Rekursiva algoritmer bygger på tanken att lösningen på ett problem kan hittas genom att hitta lösningar på mindre delproblem av samma problem. I en rekursiv algoritm definieras en funktion i form av den tidigare versionen av sig själv. Det är viktigt att notera att denna självreferens ska ha ett uppsägningstillstånd för att undvika att referera sig själv för alltid. Avslutningsvillkoren kontrolleras innan man hänvisar till sig själv. Det initiala steget i en rekursiv algoritm är relaterad till grundklausulen i den rekursiva definitionen av problemet. Stegen som följer det första steget är relaterat till problemets induktiva klausuler. Rekursiva algoritmer ger en enklare lösning i många situationer och det ligger närmare det naturliga sättet att tänka än den iterativa algoritmen för samma problem. Men i allmänhet kräver rekursiva algoritmer mer minne och de är beräkningsmässigt dyra.

Vad är skillnaden mellan en randomiserad och en rekursiv algoritm?

Slumpmässiga algoritmer är algoritmer som använder en slumpmässig känsla genom att göra slumpmässiga val som kan påverka algoritmens utförande, medan rekursiva algoritmer är algoritmer som bygger på idén att en lösning på ett problem kan hittas genom att hitta lösningar på mindre delproblem av samma problem. På grund av slumpmässigheten i de slumpmässiga algoritmerna kan algoritmens beteende förändras även för samma ingång (i olika utföranden av algoritmen). Men detta är inte möjligt i rekursiva algoritmer och beteendet hos en rekursiv algoritm skulle vara samma för en fast ingång.