Randomized vs Recursive Algorithm
Slumpmässiga algoritmer innehåller en känsla av slumpmässighet i sin logik genom att göra slumpmässiga val under utförandet av algoritmen. På grund av denna slumpmässighet kan algoritmens beteende förändras även för en fast ingång. För många problem ger randomiserade algoritmer de enklaste och effektivaste 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 programmeringsspråk på hög nivå stöder rekursion.
Vad är en slumpmässig algoritm?
Slumpmässiga 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 vanligtvis genom att ta en uppsättning slumpmässiga tal som genereras av en pseudorandomnummergenerator som en extra ingång. På grund av detta kan algoritmens beteende förä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 löptid på O (n log n) oavsett ingångsegenskaperna. Vidare används randomiserad inkrementell konstruktionsmetod för att bygga strukturer som konvex skrov i beräkningsgeometri. I denna metod permitteras ingångspunkterna slumpmässigt och införs sedan en efter en i strukturen. Att implementera en randomiserad algoritm är relativt enkel än att implementera en deterministisk algoritm för samma problem. Den största utmaningen i att designa en randomiserad algoritm ligger i att utföra asymptotisk analys för tids- 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 termer av den tidigare versionen av sig själv. Det är viktigt att notera att denna självreferens bör ha ett avslutningsvillkor för att undvika att referera till sig själv för alltid. Uppsägningsvillkoret kontrolleras innan det hänvisas till sig själv. Det första steget i en rekursiv algoritm är relaterad till grundparagrafen i den rekursiva definitionen av problemet. Stegen som följer det första steget är relaterade till de induktiva klausulerna i problemet. Rekursiva algoritmer ger en enklare lösning i många situationer och det är närmare det naturliga sättet att tänka än den iterativa algoritmen för samma problem. Men generellt,rekursiva algoritmer kräver 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 känsla av slumpmässighet genom att göra slumpmässiga val som kan påverka exekveringen av algoritmen, medan rekursiva algoritmer är algoritmer som bygger på tanken 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 (vid olika exekveringar av algoritmen). Men detta är inte möjligt i rekursiva algoritmer och beteendet hos en rekursiv algoritm skulle vara detsamma för en fast ingång.
