¿Qué es un algoritmo?
Un algoritmo es un procedimiento paso a paso para resolver un problema. Un buen algoritmo debe optimizarse en términos de tiempo y espacio. Los diferentes tipos de problemas requieren diferentes tipos de técnicas algorítmicas para resolverlos de la manera más optimizada. Hay muchos tipos de algoritmos, pero en este artículo se analizan los algoritmos más importantes y fundamentales que debe utilizar.
1. Algoritmo de fuerza bruta :
Este es el tipo de algoritmo más básico y simple. Un algoritmo de fuerza bruta es el enfoque sencillo de un problema, es decir, el primer enfoque que nos viene a la mente al ver el problema. Más técnicamente, es como iterar todas las posibilidades disponibles para resolver ese problema.
Ejemplo:
Si hay un bloqueo de PIN de 4 dígitos. Los dígitos que se elegirán del 0 al 9 luego la fuerza bruta probará todas las combinaciones posibles una por una, como 0001, 0002, 0003, 0004, y así sucesivamente hasta que obtengamos el PIN correcto. En el peor de los casos, serán necesarios 10.000 intentos para encontrar la combinación adecuada.
2. Algoritmo recursivo :
Este tipo de algoritmo se basa en recursividad . En recursión, un problema se resuelve dividiéndolo en subproblemas del mismo tipo y llamándose a uno mismo una y otra vez hasta que el problema se resuelve con la ayuda de una condición base.
Algunos problemas comunes que se resuelven utilizando algoritmos recursivos son Factorial de un número , Serie Fibonacci , Torre de Hanoi , DFS para gráfico , etc.
a) Algoritmo divide y vencerás :
En los algoritmos Divide and Conquer, la idea es resolver el problema en dos secciones, la primera sección divide el problema en subproblemas del mismo tipo. La segunda sección consiste en resolver el problema más pequeño de forma independiente y luego sumar el resultado combinado para producir la respuesta final al problema.
Algunos problemas comunes que se resuelven utilizando algoritmos de divide y vencerás son Búsqueda binaria , Combinar ordenar , Ordenación rápida, Multiplicación de matrices de Strassen , etc.
b) Algoritmos de programación dinámica :
Este tipo de algoritmo también se conoce como técnica de memorización porque en este la idea es almacenar el resultado calculado previamente para evitar calcularlo una y otra vez. En programación dinámica, divida el problema complejo en más pequeños subproblemas superpuestos y almacenar el resultado para uso futuro.
Los siguientes problemas se pueden resolver utilizando el algoritmo de programación dinámica. Problema de mochila , Programación de trabajos ponderados , Algoritmo de Floyd Warshall , etc.
C) Algoritmo codicioso :
En el algoritmo codicioso, la solución se construye parte por parte. La decisión de elegir la siguiente parte se toma sobre la base de que proporciona un beneficio inmediato. Nunca considera las opciones que se habían tomado anteriormente.
Algunos problemas comunes que se pueden resolver mediante el algoritmo codicioso son Algoritmo de ruta más corta de Dijkstra , Algoritmo de Prim , Algoritmo de Kruskal , Codificación Huffman , etc.
d) Algoritmo de retroceso :
En el algoritmo de retroceso, el problema se resuelve de forma incremental, es decir, es una técnica algorítmica para resolver problemas de forma recursiva intentando construir una solución de forma incremental, una pieza a la vez, eliminando aquellas soluciones que no satisfacen las restricciones del problema en ningún momento. punto de tiempo.
Algunos problemas comunes que se pueden resolver mediante el algoritmo de retroceso son los Ciclo hamiltoniano , Problema de coloración M , N problema de la reina , Problema de la rata en el laberinto , etc.
3. Algoritmo aleatorio :
En el algoritmo aleatorio, utilizamos un número aleatorio que ayuda a decidir el resultado esperado. La decisión de elegir el número aleatorio para que proporcione el beneficio inmediato.
Algunos problemas comunes que se pueden resolver mediante el algoritmo aleatorio son Quicksort: en Quicksort utilizamos el número aleatorio para seleccionar el pivote.
4. Algoritmo de clasificación :
El algoritmo de clasificación se utiliza para ordenar datos en orden tal vez ascendente o descendente. También se utiliza para organizar datos de una manera eficiente y útil.
Algunos problemas comunes que se pueden resolver mediante el algoritmo de clasificación son la clasificación por burbujas, la clasificación por inserción, la clasificación por combinación, la clasificación por selección y la clasificación rápida, que son ejemplos del algoritmo de clasificación.
5. Algoritmo de búsqueda :
El algoritmo de búsqueda es el algoritmo que se utiliza para buscar la clave específica en datos ordenados o no clasificados en particular. Algunos problemas comunes que se pueden resolver mediante el algoritmo de búsqueda son la búsqueda binaria o la búsqueda lineal, que es un ejemplo de algoritmo de búsqueda.
6. Algoritmo de hash :
Los algoritmos hash funcionan igual que el algoritmo de búsqueda, pero contienen un índice con un ID de clave, es decir, un par clave-valor. En hash, asignamos una clave a datos específicos.
Algunos problemas comunes se pueden resolver mediante el algoritmo Hashing en la verificación de contraseñas.