Algoritmo divide e vencerás: Diferenzas entre revisións

Con todo, este tipo de algoritmos tamén se poden implementar como un algoritmo non recursivo que almacene as solucións parciais nunha [[estrutura de datos]] explícita, como pode ser unha [[pila (estrutura de datos)|pila]], [[cola (estrutura de datos)|cola]], ou [[cola con prioridade]]. Esta aproximación dá maior liberdade ao deseñador, de forma que se poida escoller que subproblema é o que se vai a resolver a continuación, o que pode ser importante no caso de usar técnicas como [[Ramificación e anotación]] ou de optimización.

 

Este modelo algorítmico é unha ferramenta potente para solucionar problemas complexos, talles como o clásico xogo das [[torres de Hanoi]]. Todo o que necesita este algoritmo é dividir o problema en subproblemas máis sinxelos, e estes en outros máis sinxelos ata chegar a uns subproblemas sinxelos (tamén chamados casos basee). Unha vez aí, resólvense e combínanse os subproblemas en orde inversa ao seu inicio. Como dividir os problemas é, a miúdo, a parte máis complexa do algoritmo. Por iso, en moitos problemas, o modelo só ofrece a solución máis sinxela, non a mellor.

 

Normalmente, esta técnica proporciona unha forma natural de deseñar ''algoritmos eficientes''. Por exemplo, se o traballo de dividir o problema e de combinar as solucións parciais é proporcional ao tamaño do problema (''n''); ademais, hai un número limitado ''p'' de subproblemas de tamaño aproximadamente igual a ''n/p'' en cada etapa; e para rematar, os casos basee requiren un tempo constante (Ou(1)); entón o algoritmo divide e vencerás ten por [[cota superior asintótica]] a Ou(''n''log''n''). Esta cota é a que teñen os algoritmos divide e vencerás que solucionan problemas talles como ordenar e a transformada discreta de fourier. Ambos os procedementos reducen a súa complexidade, anteriormente definida por Ou(''n''<sup>2</sup >). Para terminar, cabe destacar que existen outros enfoques e métodos que melloran estas cotas.

 

Este tipo de algoritmos adáptase de forma natural á execución en contornas multiprocesador, especialmente en [[sistemas de memoria compartida]] onde a comunicación de datos entre os procesadores non necesita ser planeada por adiantado, polo que subproblemas distintos pódense executar en procesadores distintos.

 

Os algoritmos que seguen o paradigma Divide e vencerás, tenden naturalmente a facer un uso eficiente das memorias [[caché]]s. A razón é que unha vez que un subproblema é o suficientemente pequeno, el e todos os seus

subproblemas pódense, en principio, solucionar dentro desa [[caché]], sen ter acceso á [[memoria principal]], que é da orde de decenas de veces máis lenta. Un algoritmo deseñado para aproveitar a memoria caché deste xeito chámase ''[[modelo caché-olvidadiza]]'', olvidadiza porque non contén o tamaño da memoria como parámetro explícito. Por outra banda, estes algoritmos pódense deseñar para moitos problemas importantes, talles como ordenación, a multiplicación de matrices, de maneira que se faga un uso óptimo da caché. En contraste, o achegamento tradicional para explotar a caché é ''facer bloques'', desta forma, o problema divídese explicitamente nas partes de tamaños apropiados para que se poida utilizar ao caché de forma óptima, pero soamente cando o algoritmo é mellorado para o tamaño específico da caché dunha máquina particular.

Con todo, a clase de optimalidad asintótica descrita aquí, análoga a [[cota superior asintótica|notación Ou maiúscula]], non fai caso de factores constantes, e o engadir melloras adicionais específicas da máquina e caché non é un requirimento para alcanzar o óptimo nun sentido absoluto.

 

A principal desvantaxe deste método é a súa lentitude na repetición do proceso recursivo: os gastos indirectos das chamadas recursivas á resolución dos subproblemas, xunto co feito de ter que almacenar a pila de

chamadas (o estado en cada punto na repetición), poden empeorar calquera mellora ata entón lograda.

Esta tara, con todo, depende do estilo da implementación: con casos basee o suficientemente grandes, redúcense os gastos indirectos da repetición das chamadas.

 

 

 

[[Categoría:Algoritmos|Algoritmo divide e venceras]]

[[pt:Divisão e conquista]]

[[ro:Divide et impera (informatică)]]

[[sl:Deli in vladaj (računalništvo)]]

[[sr:Подели па владај (информатика)]]