Un algoritmo híbrido es un algoritmo que combina dos o más algoritmos que resuelven el mismo problema, ya sea eligiendo uno en función de alguna característica de los datos o alternando entre ellos a lo largo del algoritmo. Esto se hace generalmente para combinar las características deseadas de cada uno, de modo que el algoritmo general sea mejor que los componentes individuales.
"Algoritmo híbrido" no se refiere simplemente a la combinación de múltiples algoritmos para resolver un problema diferente (muchos algoritmos pueden considerarse como combinaciones de piezas más simples), sino únicamente a la combinación de algoritmos que resuelven el mismo problema, pero difieren en otras características, especialmente el rendimiento.
En informática , los algoritmos híbridos son muy comunes en las implementaciones optimizadas en el mundo real de algoritmos recursivos , particularmente en las implementaciones de algoritmos de divide y vencerás o decrece y vencerás , donde el tamaño de los datos disminuye a medida que uno se adentra más en la recursión. En este caso, se utiliza un algoritmo para el enfoque general (en datos grandes), pero en lo profundo de la recursión, cambia a un algoritmo diferente, que es más eficiente en datos pequeños. Un ejemplo común es en los algoritmos de ordenamiento , donde el ordenamiento por inserción, que es ineficiente en datos grandes, pero muy eficiente en datos pequeños (digamos, de cinco a diez elementos), se utiliza como paso final, después de aplicar principalmente otro algoritmo, como el ordenamiento por fusión o el ordenamiento rápido . El ordenamiento por fusión y el ordenamiento rápido son asintóticamente óptimos en datos grandes, pero la sobrecarga se vuelve significativa si se aplican a datos pequeños, de ahí el uso de un algoritmo diferente al final de la recursión. Un algoritmo de ordenamiento híbrido altamente optimizado es Timsort , que combina el ordenamiento por fusión y el ordenamiento por inserción, junto con lógica adicional (incluida la búsqueda binaria ) en la lógica de fusión.
Un procedimiento general para un algoritmo recursivo híbrido simple es cortocircuitar el caso base, también conocido como recursión a distancia . En este caso, se comprueba si el siguiente paso dará como resultado el caso base antes de la llamada a la función, lo que evita una llamada a la función innecesaria. Por ejemplo, en un árbol, en lugar de recurrir a un nodo secundario y luego verificar si es nulo, se comprueba si es nulo antes de recurrir. Esto es útil para la eficiencia cuando el algoritmo suele encontrar el caso base muchas veces, como en muchos algoritmos de árbol, pero de lo contrario se considera un estilo deficiente, particularmente en el ámbito académico, debido a la complejidad añadida.
Otro ejemplo de algoritmos híbridos por razones de rendimiento son introsort e introselect , que combinan un algoritmo para un rendimiento promedio rápido y recurren a otro algoritmo para garantizar un rendimiento óptimo (asintóticamente) en el peor de los casos. Introsort comienza con un quicksort , pero cambia a un heap sort si el quicksort no progresa bien; análogamente, introselect comienza con quickselect , pero cambia a median of medians si quickselect no progresa bien.
Los algoritmos distribuidos centralizados a menudo pueden considerarse como algoritmos híbridos, que consisten en un algoritmo individual (que se ejecuta en cada procesador distribuido) y un algoritmo de combinación (que se ejecuta en un distribuidor centralizado); estos corresponden respectivamente a la ejecución de todo el algoritmo en un procesador o a la ejecución de todo el cálculo en el distribuidor, combinando resultados triviales (un conjunto de datos de un elemento de cada procesador). Un ejemplo básico de estos algoritmos son las ordenaciones de distribución , que se utilizan particularmente para la ordenación externa , que dividen los datos en subconjuntos separados, ordenan los subconjuntos y luego combinan los subconjuntos en datos totalmente ordenados; los ejemplos incluyen la ordenación por cubo y la ordenación flash .
Sin embargo, en general, los algoritmos distribuidos no tienen por qué ser algoritmos híbridos, ya que los algoritmos individuales o los algoritmos de combinación o comunicación pueden resolver problemas diferentes. Por ejemplo, en modelos como MapReduce , los pasos Map y Reduce resuelven problemas diferentes y se combinan para resolver un tercer problema diferente.