Algoritme aleatori versus recursiu
Els algorismes aleatoris incorporen una sensació d'aleatorietat en la seva lògica fent eleccions aleatòries durant l'execució de l'algorisme. A causa d'aquesta aleatorietat, el comportament de l'algorisme pot canviar fins i tot per a una entrada fixa. Per a molts problemes, els algorismes aleatoris proporcionen les solucions més senzilles i eficients. Els algorismes recursius es basen en la idea que la solució a un problema es pot trobar trobant solucions a subproblemes més petits del mateix problema. La recursivitat s'utilitza àmpliament per trobar solucions a problemes en informàtica i molts llenguatges de programació d' alt nivell admeten la recursivitat.
Què és un algorisme aleatori?
Els algorismes aleatoris incorporen una sensació d'aleatorietat fent eleccions aleatòries que guien l'execució de l'algorisme. Això es fa normalment prenent un conjunt de números aleatoris generats per un generador de números pseudoaleatoris com a entrada addicional. A causa d'això, el comportament de l'algorisme pot canviar fins i tot per a una entrada fixa. Quicksort és un algorisme àmpliament conegut que utilitza el concepte d'aleatorietat i té un temps d'execució de O(n log n) independentment de les propietats d'entrada. A més, el mètode de construcció incremental aleatoritzat s'utilitza per construir estructures com el casc convex en la geometria computacional. En aquest mètode, els punts d'entrada es permuten aleatòriament i després s'insereixen un per un a l'estructura. Implementar un algorisme aleatori és relativament senzill que implementar un algorisme determinista per al mateix problema. El repte més gran en el disseny d'un algorisme aleatori rau en realitzar anàlisis asimptòtiques per a la complexitat del temps i l'espai.
Què és un algorisme recursiu?
Els algorismes recursius es basen en la idea que la solució a un problema es pot trobar trobant solucions a subproblemes més petits del mateix problema. En un algorisme recursiu, una funció es defineix en termes de la versió anterior de si mateixa. És important tenir en compte que aquesta autoreferència hauria de tenir una condició de terminació per evitar la referència per sempre. La condició de terminació es comprova abans de fer referència a si mateixa. El pas inicial d'un algorisme recursiu està relacionat amb la clàusula base de la definició recursiva del problema. Els passos que segueixen el pas inicial estan relacionats amb les clàusules inductives del problema. Els algorismes recursius proporcionen una solució més senzilla en moltes situacions i s'acosta més a la forma natural de pensar que l'algorisme iteratiu per al mateix problema. Però, en general, els algorismes recursius requereixen més memòria i són computacionalment costosos.
Quina diferència hi ha entre un algorisme aleatori i un recursiu?
Els algorismes aleatoris són algorismes que utilitzen una sensació d'aleatorietat fent eleccions aleatòries que podrien afectar l'execució de l'algorisme, mentre que els algorismes recursius són algorismes que es basen en la idea que es pot trobar una solució a un problema trobant solucions a subproblemes més petits del mateix problema. A causa de l'aleatorietat dels algorismes aleatoris, el comportament de l'algoritme podria canviar fins i tot per a la mateixa entrada (en diferents execucions de l'algorisme). Però això no és possible en algorismes recursius i el comportament d'un algorisme recursiu seria el mateix per a una entrada fixa.
