Gerandomiseerd versus recursief algoritme
Gerandomiseerde algoritmen nemen een gevoel van willekeur in de logica op door willekeurige keuzes te maken tijdens de uitvoering van het algoritme. Vanwege deze willekeur kan het gedrag van het algoritme zelfs voor een vaste invoer veranderen. Voor veel problemen bieden gerandomiseerde algoritmen de eenvoudigste en meest efficiënte oplossingen. Recursieve algoritmen zijn gebaseerd op het idee dat de oplossing voor een probleem kan worden gevonden door oplossingen te vinden voor kleinere deelproblemen van hetzelfde probleem. Recursie wordt veel gebruikt om oplossingen te vinden voor problemen in de informatica en veel programmeertalen op hoog niveau ondersteunen recursie.
Wat is een gerandomiseerd algoritme?
Gerandomiseerde algoritmen bevatten een gevoel van willekeur door willekeurige keuzes te maken die de uitvoering van het algoritme sturen. Dit wordt meestal gedaan door een reeks willekeurige getallen die door een pseudowillekeurige getalgenerator zijn gegenereerd als extra invoer te nemen. Hierdoor kan het gedrag van het algoritme zelfs voor een vaste invoer veranderen. Quicksort is een algemeen bekend algoritme dat het concept van willekeur gebruikt en een looptijd heeft van O (n log n), ongeacht de invoereigenschappen. Verder wordt een willekeurige incrementele constructiemethode gebruikt voor het bouwen van constructies zoals een convexe romp in de berekeningsgeometrie. Bij deze methode worden de invoerpunten willekeurig gepermuteerd en vervolgens één voor één in de structuur ingevoegd. Het implementeren van een willekeurig algoritme is relatief eenvoudig dan het implementeren van een deterministisch algoritme voor hetzelfde probleem. De grootste uitdaging bij het ontwerpen van een gerandomiseerd algoritme ligt in het uitvoeren van asymptotische analyses voor de complexiteit van tijd en ruimte.
Wat is een recursief algoritme?
Recursieve algoritmen zijn gebaseerd op het idee dat de oplossing voor een probleem kan worden gevonden door oplossingen te vinden voor kleinere deelproblemen van hetzelfde probleem. In een recursief algoritme wordt een functie gedefinieerd in termen van de eerdere versie van zichzelf. Het is belangrijk op te merken dat deze zelfverwijzing een beëindigingsvoorwaarde moet hebben om te voorkomen dat er voor altijd naar zichzelf wordt verwezen. De beëindigingsvoorwaarde wordt gecontroleerd voordat naar zichzelf wordt verwezen. De eerste stap van een recursief algoritme is gerelateerd aan de basisclausule van de recursieve definitie van het probleem. De stappen die volgen op de eerste stap houden verband met de inductieve clausules van het probleem. Recursieve algoritmen bieden in veel situaties een eenvoudigere oplossing en liggen dichter bij de natuurlijke manier van denken dan het iteratieve algoritme voor hetzelfde probleem. Maar in het algemeen,recursieve algoritmen vereisen meer geheugen en zijn rekenkundig duur.
Wat is het verschil tussen een gerandomiseerd en een recursief algoritme?
Willekeurige algoritmen zijn algoritmen die een gevoel van willekeur gebruiken door willekeurige keuzes te maken die de uitvoering van het algoritme kunnen beïnvloeden, terwijl recursieve algoritmen algoritmen zijn die zijn gebaseerd op het idee dat een oplossing voor een probleem kan worden gevonden door oplossingen te vinden voor kleinere deelproblemen. van hetzelfde probleem. Vanwege de willekeur in de willekeurige algoritmen, kan het gedrag van het algoritme zelfs voor dezelfde invoer veranderen (in verschillende uitvoeringen van het algoritme). Maar dit is niet mogelijk in recursieve algoritmen en het gedrag van een recursief algoritme zou hetzelfde zijn voor een vaste invoer.
