Ejemplo 1: elemento mayoritario
Ejemplo 2: algoritmo de ordenación quickSort
Este tipo de algoritmos se usa en la resolución de problemas que pueden ser simplificados en problemas más sencillos, cuando hablo de simplificación del problema me refiero a reducir el volumen de datos manejados.
Se pueden distinguir tres partes fundamentales:
- Los casos base: son las sentencias que se ejecutarán cuando no sea posible reducir más el problema
- La simplificación del problema: es un bloque de instrucciones cuya finalidad es dividir el problema en subproblemas menores del mismo tipo.
- La parte recursiva: consiste en hacer una llamada a la propia función para que trabaje sobre los subproblemas obtenidos anteriormente.
Ejemplo 1:
Se quiere encontrar un algoritmo para obtener, si lo hay, el elemento mayoritario de una colección de números enteros.Se considera elemento mayoritario a aquel que aparece más de n/2 veces, donde n es la cantidad de elementos de la colección de datos.
En la imagen se muestra el diagrama de flujo del algoritmo implementado para la resolución del problema.
public class Mayoritario { /** * Excepción personalizada que se lanza cuando no hay elemento mayoritario **/ public static class NoMayoritarioException extends Exception{ public NoMayoritarioException(){ super("No hay elementos mayoritarios"); } } /** * Devuelve un entero correspondiente al elemento mayoritario de un *ArrayList de enteros. *¡Ojo porque el contenido del ArrayList se pierde! * @param cjto Si quiere conservar los datos pase una copia del original * @return * @throws mayoritario.Mayoritario.NoMayoritarioException */ public int calcMayoritario(ArrayList<Integer> cjto)throws NoMayoritarioException{ //Inicio de los casos base if(cjto.size()<2){ throw new NoMayoritarioException(); } switch(cjto.size()){ case 2: if(cjto.get(0) ==cjto.get(1)) { return cjto.get(0); } throw new NoMayoritarioException(); case 3: if(cjto.get(0) ==cjto.get(1)||cjto.get(0) ==cjto.get(2)) { return cjto.get(0); }else if(cjto.get(2) ==cjto.get(1)){ return cjto.get(1); } throw new NoMayoritarioException(); } if(cjto.size()==2){ } //Selección de candidatos ArrayList<Integer> candidatos; candidatos = new ArrayList<>(); for(int i=0;i<cjto.size()-2;i+=3){ if(cjto.get(i) ==cjto.get(i+1) || cjto.get(i) ==cjto.get(i+2)){ candidatos.add(cjto.get(i)); }if(cjto.get(i+1) ==cjto.get(i+2)){ candidatos.add(cjto.get(i+1)); } } int len=cjto.size(); if(len%2==0 && cjto.get(len-2) ==cjto.get(len-1)){ candidatos.add(cjto.get(len-1)); } //Aplico la recursión if(candidatos.size()>=cjto.size()/2){ //Alivio un poco la carga espacial, con lo que se pierden los datos de partida cjto=null; return this.calcMayoritario(candidatos); }else{ throw new NoMayoritarioException(); } } }
Comparación con otras alternativas
Al aplicar este algoritmo en cada llamada a la función se recorre una sola vez la colección de datos y de una a otra llamada el número de elementos es como mucho la mitad del anterior.Las alternativas más directas para resolver este problema sin usar un algoritmo de este tipo pasarían por recorrer todos los elementos hasta encontrar uno que se repita más de n/2 veces. El caso más favorable es cuando el primer elemento es el mayoritario por lo que tendrá complejidad lineal, pero en el resto de casos será cuadrática
Otra opción pasa por ordenar primero la colección, pero habría que tener en cuenta la complejidad del algoritmo de ordenación.
Otra posibilidad sería utilizar un algoritmo dinámico que se apoyase en una colección de posibles soluciones, donde cada elemento está compuesto por el valor y el número de repeticiones. En ese caso se recorrería una sola vez la colección inicial y un máximo de n veces, en el peor de los casos, la colección auxiliar para comprobar si el valor i-ésimo ya se encuentra en la colección auxiliar e insertarlo o incrementar el valor de sus repeticiones. Por lo que tanto la complejidad espacial como temporal serán mayores.
Ejemplo 2: algoritmo quickSort
El algoritmo quickSort es uno de los casos más típicos de aplicación de algoritmos del tipo divide y vencerás. Consiste en la ordenación de una colección indexada de objetos dividiendo de forma recursiva la colección en subconjuntos que se caracterizan porque los elementos del subconjunto anterior aun elemento dado, pivote, son menores que este y los del subconjunto posterior son mayores. Al hacer subconjuntos de los subconjuntos de forma recursiva se logra dividir el problema en muchos subproblemas triviales.Cabe destacar que con este algoritmo no es necesario un paso posterior de mezcla para obtener la colección ordenada.
La complejidad del algoritmo es cuadrática en el peor de los casos y nLogn en los casos mejor y medio. El caso será mejor o peor en función de la distancia entre el pivote elegido y la mediana del conjunto de datos, cuanto más alejado peor. En la implementación que se muestra a continuación se escoge como pivote al primer elemento del subconjunto, por lo que este algoritmo es susceptible de ser optimizado sin mucho esfuerzo, aunque hay que tener en cuenta la complejidad del algoritmo de elección del pivote para estimar la eficiencia final del nuevo algoritmo.
public static void quickSort(int[] a,int prim, int ult){
if(prim<ult){
//Genero subconjuntos
int l=pivote(a,prim,ult);
//Aplico recursión sobre los subconjuntos
if(l>prim){quickSort(a,prim,l-1);}
if(l<ult){quickSort(a,l+1,ult);}
}//Caso base prim=ult
}
/**
* Devuelve la posición del pivote, elemento que por la izquierda solo
* tiene elementos de valor inferior y por la derecha de valor superior.
* Sobra decir que lo que hace es colocar los elementos a derecha o
* del pivote según su valor.
*/
private static int pivote(int[] a,int prim, int ult){
int i=prim+1;
int l=ult;
while(a[i]<=a[prim] && i<ult){i++;}
while(a[l]>a[prim]){l--;}
while(i<l){
intercambia(a,i,l);
while(a[i]<=a[prim]){i++;}
while(a[l]>a[prim]){l--;}
}
intercambia(a,prim,l);
return l;
}
No hay comentarios:
Publicar un comentario