Algorisme divideix i venceràs
From Wikipedia, the free encyclopedia
En el camp de les ciències de la computació, el terme divideix i venceràs (DiV) fa referència a un dels paradigmes més importants de disseny algorítmic. El mètode es basa en la resolució recursiva d'un problema dividint-lo en dos o més subproblemes d'igual tipus o similar. El procés continua fins que els subproblemes arriben a ser prou senzills perquè es resolguin directament. Al final, les solucions de cadascun dels subproblemes es combinen per donar la solució del problema original.
Aquest article o secció no cita les fonts o necessita més referències per a la seva verificabilitat. |
Aquest article tracta sobre el paradigma informàtic. Si cerqueu l'estratègia política, vegeu «Divide et impera». |
La denominació s'inspira amb la locució llatina divide et impera, una estratègia política popular des de l'edat antiga: qui vol vèncer un poble enemic o un adversari fort ha de dedicar-se a dividir-lo.[1]
Aquesta tècnica és la base dels algorismes eficients per gairebé qualsevol tipus de problema com, per exemple, algorismes d'ordenació (quicksort, mergesort, entre molts altres), multiplicació nombres grans (Karatsuba), anàlisis sintàctiques (anàlisi sintàctica top-down), la transformada discreta de Fourier etc.
D'altra banda, analitzar i dissenyar algorismes de DIV es una tasca que porta temps dominar-la. De la mateixa forma que en la inducció, a vegades és necessari substituir el problema original per un de més complex per aconseguir realitzar la recursió, i no hi ha un mètode sistemàtic general.
El nom divideix i venceràs també s'aplica de vegades a algorismes que redueixen cada problema a un únic subproblema, com la cerca binària per trobar un element en una llista ordenada (o el seu equivalent en computació numèrica, l'algorisme de bisecció per a la cerca d'arrels). Aquests algorismes poden ser implementats més eficientment que els algorismes generals de “divideix i venceràs”; en particular, si s'utilitza una sèrie de recursions que converteixen l'algorisme en simples bucles. Sota aquesta àmplia definició però, cada algorisme que utilitza recursió o bucles es pot prendre com un algorisme de “divideix i venceràs”. El nom decrementa i venceràs ha estat proposat per a la subclasse simple de problemes.
La correcció d'un algorisme de “divideix i venceràs”, es demostra habitualment per mitjà de l'inducció matemàtica, i el seu cost computacional es determina resolent relacions de recurrència.