Clasificación de Algoritmos con Ejemplos

Hay muchas formas de clasificar los algoritmos y algunas de ellas se muestran a continuación:

1. Método de implementación
2. Método de diseño
3. Otras clasificaciones

Clasificación por Método de Implementación:

1. Recursividad o Iteración

• Un algoritmo recursivo es aquel que se llama a sí mismo repetidamente hasta que se satisface una condición base. Es un método común utilizado en lenguajes de programación funcional como C, C++ , etc.
• Los algoritmos iterativos usan construcciones como bucles y, a veces, otras estructuras de datos como pilas y colas para resolver los problemas.
• Algunos problemas son adecuados para recursivos y otros para iterativos. Por ejemplo, el problema de las Torres de Hanoi se puede entender fácilmente en una implementación recursiva. Cada versión recursiva tiene una versión iterativa y viceversa.

2. Procesal o Declarativa (no Procesal)-

• En los lenguajes de programación declarativos, decimos lo que queremos sin tener que decir cómo hacerlo.
• Con la programación procedimental, tenemos que especificar los pasos exactos para obtener el resultado. Por ejemplo, SQL es más declarativo que de procedimiento, porque las consultas no especifican los pasos para producir el resultado. Los ejemplos de lenguajes de procedimiento incluyen C, PHP y PERL.

3. Serial o Paralelo o Distribuido-

• En general, mientras discutimos los algoritmos, asumimos que las computadoras ejecutan una instrucción a la vez. Estos se llaman algoritmos seriales.
• Los algoritmos paralelos aprovechan las arquitecturas informáticas para procesar varias instrucciones a la vez. Dividen el problema en subproblemas y los sirven a varios procesadores o hilos. Los algoritmos iterativos generalmente están paralelizados.
• Si los algoritmos paralelos se distribuyen a diferentes máquinas, los llamamos algoritmos distribuidos.

4. Determinista o no determinista-

• Los algoritmos deterministas resuelven el problema con un proceso predefinido, mientras que los algoritmos no deterministas adivinan la mejor solución en cada paso mediante el uso de heurísticas.

5. Exacto o Aproximado-

• Los algoritmos para los que somos capaces de encontrar las soluciones óptimas se denominan algoritmos exactos. En informática, si no tenemos la solución óptima, damos algoritmos de aproximación.
• Los algoritmos de aproximación generalmente se asocian con problemas NP-difíciles.

Clasificación por método de diseño:

Otra forma de clasificar los algoritmos es por su método de diseño.

1. Método codicioso-

• Algoritmos codiciosos Funcionan por etapas.
• En cada etapa se toma una decisión que es buena en ese momento, sin preocuparse por las consecuencias futuras.
• En general, esto significa que se elige algo mejor local. Asume que la mejor selección local también contribuye a la solución óptima global.

2. Divide y vencerás-

La estrategia Divide y vencerás resuelve un problema al:

1. Dividir: dividir el problema en subproblemas que son instancias más pequeñas del mismo tipo de problema.
2. Recursión: Resolver recursivamente estos subproblemas.
3. Conquistar: Combinando apropiadamente sus respuestas.

Ejemplos: algoritmos de búsqueda binaria y ordenación por fusión.

3. Programación dinámica-

• La programación dinámica (DP) y la memorización trabajan juntas. La diferencia entre DP y divide y vencerás es que en el caso de este último no hay dependencia entre los subproblemas, mientras que en DP habrá superposición de subproblemas. Mediante el uso de la memorización [manteniendo una tabla para los subproblemas ya resueltos], DP reduce la complejidad exponencial a la complejidad polinomial (O(n2), O(n3), etc.) para muchos problemas.
• La diferencia entre programación dinámica y recursión está en la memorización de llamadas recursivas. Cuando los subproblemas son independientes y si no hay repetición, la memorización no
• Ayuda, por lo tanto, la programación dinámica no es una solución para todos los problemas.
• Mediante el uso de la memorización [manteniendo una tabla de subproblemas ya resueltos], la programación dinámica reduce la complejidad de exponencial a polinomial.

4. Programación lineal-

• En la programación lineal, existen desigualdades en términos de entradas y maximización (o minimización) de alguna función lineal de las entradas.
• Muchos problemas (ejemplo: flujo máximo para gráficos dirigidos) pueden discutirse usando programación lineal.

5. Reducción [Transformar y Conquistar]

• En este método, resolvemos un problema difícil transformándolo en un problema conocido para el cual tenemos algoritmos asintóticamente óptimos. En este método, el objetivo es encontrar un algoritmo reductor cuya complejidad no esté dominada por los algoritmos reducidos resultantes. Por ejemplo, el algoritmo de selección para encontrar la mediana en una lista implica primero ordenar la lista y luego encontrar el elemento central en la lista ordenada. Estas técnicas también se denominan transformar y conquistar.

Otras clasificaciones:

1. Clasificación por Área de Investigación-

• En informática, cada campo tiene sus propios problemas y necesita algoritmos eficientes. Ejemplos: algoritmos de búsqueda, algoritmos de clasificación, algoritmos de combinación, algoritmos numéricos, algoritmos gráficos, algoritmos de strings, algoritmos geométricos, algoritmos combinatorios, aprendizaje automático, criptografía, algoritmos paralelos, algoritmos de compresión de datos, técnicas de análisis y más.

2. Clasificación por Complejidad-

• En esta clasificación, los algoritmos se clasifican por el tiempo que tardan en encontrar una solución en función de su tamaño de entrada. Algunos algoritmos toman complejidad de tiempo lineal (O(n)) y otros toman tiempo exponencial, y algunos nunca se detienen. Tenga en cuenta que algunos problemas pueden tener múltiples algoritmos con diferentes complejidades.

3. Algoritmos aleatorios-

• Algunos algoritmos toman decisiones al azar. Para algunos problemas, las soluciones más rápidas deben involucrar la aleatoriedad. Ejemplo: Clasificación rápida.