Randomiserad vs rekursiv algoritm
Randomiserade algoritmer införlivar en känsla av slumpmässighet i sin logik genom att göra slumpmässiga val under exekveringen av algoritmen. På grund av denna slumpmässighet kan beteendet hos algoritmen ä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å idén 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ögnivåprogrammeringsspråk stödjer rekursion.
Vad är en randomiserad algoritm?
Randomiserade algoritmer införlivar en känsla av slumpmässighet genom att göra slumpmässiga val som styr exekveringen av algoritmen. Detta görs vanligtvis genom att ta en uppsättning slumptal genererade av en pseudoslumptalsgenerator som en extra ingång. På grund av detta kan beteendet hos algoritmen ändras även för en fast ingång. Quicksort är en allmänt känd algoritm som använder begreppet slumpmässighet och den har en körtid på O(n log n) oavsett indataegenskaper. Vidare används randomiserad inkrementell konstruktionsmetod för att bygga strukturer som konvexa skrov i beräkningsgeometri. I denna metod permuteras inmatningspunkterna slumpmässigt och infogas sedan en efter en i strukturen. Att implementera en randomiserad algoritm är relativt enkelt än att implementera en deterministisk algoritm för samma problem. Den största utmaningen med att designa en randomiserad algoritm ligger i att utföra asymptotisk analys för tid och rumskomplexitet.
Vad är en rekursiv algoritm?
Rekursiva algoritmer är baserade på idén 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älvhänvisning bör ha ett uppsägningsvillkor för att undvika att referera sig själv för alltid. Uppsägningsvillkoret kontrolleras innan du refererar till sig själv. Det första steget i en rekursiv algoritm är relaterat till grundsatsen i den rekursiva definitionen av problemet. Stegen som följer det inledande steget är relaterade till de induktiva klausulerna i problemet. Rekursiva algoritmer ger en enklare lösning i många situationer och den 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 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å 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 beteendet hos algoritmen ändras även för samma indata (i 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.
