Como vimos en el Capítulo anterior, la técnica de Divide y Conquista se basa en subdividir un problema en problemas más pequeños similares e independientes entre sí, resolver estos problemas más pequeños y posteriormente juntar esas soluciones parciales (las soluciones de los subproblemas) en una única solución al problema mayor.
Hemos analizado el caso de la Búsqueda Binaria donde se pedía como pre condición que la cadena de números estuviera ordenada. En los próximos capítulos analizaremos métodos de ordenamiento eficientes que utilizan la técnica DyC: MergeSort y QuickSort.
En este capítulo, emplearemos Divide y Conquista para resolver el problema de determinar si una cadena de números está o no ordenada. Presentamos a continuación el pseudocódigo
Para realizar el análisis de complejidad temporal, considerar que el método "obtenerSecuencia" es constante.
El algoritmo puede ser encuadrado entonces en el Caso 2 de métodos recurrentes, con lo cual si a = 2, b = 2 y k = 0, obtenemos un costo para el método de O(n)
En el próximo capítulo veremos algunos ejemplos más de aplicación para DyC
No hay comentarios:
Publicar un comentario