Agregar a favoritos      Ayuda      Português      Ingles     

Programación - Método Divide y vencerás

Enviado por Pablo Turmero



Monografias.com
1 Método general La técnica divide y vencerás consiste en descomponer el problema en un conjunto de subproblemas más pequeños. Después se resuelven estos subproblemas y se combinan las soluciones para obtener la solución para el problema original. Esquema general: divide_venceras (p: problema) dividir (p, p1, p2, ..., pk) para i = 1, 2, ..., k si = resolver (pi) solucion = combinar (s1, s2, ..., sk) Puede ser recursivo siendo “resolver” una nueva llamada a “divide_venceras” Si el problema es “pequeño”, entonces se puede resolver de forma directa. Ejemplo: Torres de Hanoi
Monografias.com
2 Método general Para que pueda aplicarse la técnica divide y vencerás necesitamos: El problema original debe poder dividirse fácilmente en un conjunto de subproblemas, del mismo tipo que el problema original pero con una resolución más sencilla (menos costosa). La solución de un subproblema debe obtenerse independientemente de los otros. Normalmente los subproblemas deben ser de tamaños parecidos. Como mínimo necesitamos que haya dos subproblemas. Si sólo tenemos un subproblema hablamos de técnicas de reducción (o simplificación). Necesitamos un método (más o menos directo) de resolver los problemas de tamaño pequeño. Es necesario tener un método de combinar los resultados de los subproblemas.
Monografias.com
3 Método general, esquema recursivo Normalmente para resolver los subproblemas se utilizan llamadas recursivas al mismo algoritmo (aunque no necesariamente). Esquema recursivo (con división en 2 subproblemas): divide_venceras (p, q: indice) var m: indice si pequeño (p, q) solucion = solucion_directa (p, q) en otro caso m = dividir (p, q); solucion = combinar (divide_venceras (p, m), divide_venceras (m+1, q));
Monografias.com
4 Análisis de tiempos de ejecución Para el esquema recursivo, con división en dos subproblemas: g(n) Si n?n0 es suficientemente pequeño t(n) = 2*t(n/2) + f(n) En otro caso t(n): tiempo de ejecución del algoritmo. g(n): tiempo de comprobar si es pequeño y calcular la solución para el caso base f(n): tiempo de comprobar si es pequeño y de dividir el problema y combinar los resultados.
Monografias.com
5 Análisis de tiempos de ejecución Desarrollando tenemos: Suponiendo que n es potencia de 2, n = 2k, y n0 = n/2m. Si n0=1, entonces m=k:
Monografias.com
6 Análisis de tiempos de ejecución Ejemplo 1. La resolución directa se puede hacer en un tiempo constante y la combinación de resultados también. g(n) = c; f(n) = d Ejemplo 2. La solución directa se calcula en O(n2) y la combinación en O(n). g(n) = c·n2; f(n) = d·n
Monografias.com
7 Análisis de tiempos de ejecución Si el problema se divide en a llamadas recursivas de tamaño n/b, y la combinación requiere f(n) = d·n ? O(n), entonces: t(n) = a·t(n/b) + d·n Suponiendo n = bk ? k = logb n t(bk) = a·t(bk-1) + d·bk Podemos deducir que: O(nlogba) Si a > b t(n) ? O(n·log n) Si a = b O(n) Si a < b Ejemplo 3. Dividimos en 2 trozos de tamaño n/2 (ordenación por mezcla): a = b = 2 t(n) ? O(n·log n) Ejemplo 4. Realizamos 4 llamadas recursivas con trozos de tamaño n/2. a = 4; b = 2 t(n) ? O(nlog24) = O(n2)
Monografias.com
8 Búsqueda del máximo y del mínimo Método directo: MaxMin (A: array [1..N] of tipo; var Max, Min: tipo) Max = A[1] Min = A[1] para i=2, 3, ..., N si A[i]>Max Max = A[i] en otro caso si A[i]

Comentarios


Trabajos relacionados

Ver mas trabajos de Programacion

 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.


Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Iniciar sesión

Ingrese el e-mail y contraseña con el que está registrado en Monografias.com

   
 

Regístrese gratis

¿Olvidó su contraseña?

Ayuda