Algoritmo de división y conquista
Un paradigma algorítmico muy popular, un típico algoritmo de división y conquista resuelve un problema utilizando los siguientes tres pasos:
- Dividir: Dividir el problema dado en subproblemas del mismo tipo.
- Conquistar: Resolver recursivamente estos subproblemas
- Combinar: Combinar adecuadamente las respuestas
Los siguientes son algunos algoritmos estándar que son algoritmos de Dividir y Conquistar:
1 – La Búsqueda Binaria es un algoritmo de búsqueda. En cada paso, el algoritmo compara el elemento de entrada x con el valor del elemento del medio en el array. Si los valores coinciden, devuelve el índice del medio. De lo contrario, si x es menor que el elemento del medio, entonces el algoritmo recurre al lado izquierdo del elemento del medio, de lo contrario recurre al lado derecho del elemento del medio.
2 – Quicksort es un algoritmo de ordenación. El algoritmo elige un elemento pivote, reordena los elementos de la matriz de tal manera que todos los elementos más pequeños que el elemento pivote elegido se mueven al lado izquierdo del pivote, y todos los elementos mayores se mueven al lado derecho. Finalmente, el algoritmo ordena recursivamente los subarreglos a la izquierda y a la derecha del elemento pivote.
3 – Merge Sort es también un algoritmo de ordenación. El algoritmo divide el array en dos mitades, las ordena recursivamente y finalmente fusiona las dos mitades ordenadas.
4 – Pares de puntos más cercanos: El problema consiste en encontrar el par de puntos más cercano en un conjunto de puntos en el plano x-y. El problema se puede resolver en tiempo O(n²) calculando las distancias de cada par de puntos y comparando las distancias para encontrar el mínimo. El algoritmo Divide y vencerás resuelve el problema en tiempo O(nLogn).
5 – El Algoritmo de Strassen es un algoritmo eficiente para multiplicar dos matrices. Un método simple para multiplicar dos matrices necesita 3 bucles anidados y es O(n³). El algoritmo de Strassen multiplica dos matrices en tiempo O(n².8974).
6 – El algoritmo de la transformada rápida de Fourier (FFT) de Cooley-Tukey es el algoritmo más común para la FFT. Es un algoritmo de divide y vencerás que funciona en tiempo O(nlogn).
7 – Algoritmo Karatsuba para la multiplicación rápida: Realiza la multiplicación de dos números de n dígitos en un máximo de 3n^(log 3) multiplicaciones de un solo dígito en general (y exactamente n^(log3) cuando n es una potencia de 2). Por lo tanto, es más rápido que el algoritmo clásico, que requiere n² productos de un solo dígito.
Problema de las inversiones del recuento
Consideraremos un problema que surge en el análisis de los rankings, que están adquiriendo importancia para una serie de aplicaciones actuales. Por ejemplo, varios sitios en la Web hacen uso de una técnica conocida como filtrado colaborativo, en la que intentan hacer coincidir sus preferencias (de libros, películas, restaurantes) con las de otras personas en Internet. Una vez que el sitio web ha identificado a las personas con gustos «similares» a los suyos -basándose en una comparación de cómo usted y ellos califican diversas cosas-, puede recomendar nuevas cosas que les hayan gustado a esas otras personas. Otra aplicación surge en las herramientas de búsqueda recta en la Web, que ejecutan la misma consulta en muchos motores de búsqueda diferentes y luego tratan de sintetizar los resultados buscando similitudes y diferencias entre las diversas clasificaciones que devuelven los motores de búsqueda.
Un problema central en aplicaciones como ésta es el de comparar dos clasificaciones. Usted clasifica un conjunto de películas rt, y luego un sistema de filtrado colaborativo consulta su base de datos para buscar a otras personas que tuvieron clasificaciones «similares». Pero, ¿cuál es una buena manera de medir, numéricamente, la similitud de las clasificaciones de dos personas? Está claro que una clasificación idéntica es muy similar, y una clasificación completamente invertida es muy diferente; queremos algo que interpola a través de la región media.
Consideremos la comparación de su clasificación y la clasificación de un extraño del mismo conjunto de n películas. Un método natural sería etiquetar las películas del 1 al n según tu clasificación, luego ordenar estas etiquetas según la clasificación del desconocido, y ver cuántos pares están «fuera de orden». Más concretamente, consideraremos el siguiente problema. Nos dan una secuencia de n números a1, …, an; supondremos que todos los números son distintos. Queremos definir una medida que nos diga lo lejos que está esta lista de estar en orden ascendente; el valor de la medida debe ser 0 si a1 < a2 << an, y debe aumentar a medida que los números están más revueltos.
Una forma natural de cuantificar esta noción es contando el número de inversiones. Decimos que dos índices i < j forman una inversión si ai > aj, es decir, si los dos elementos ai y aj están «fuera de orden». Buscaremos determinar el número de inversiones en la secuencia a1, …, an.