La programación utiliza algoritmos con frecuencia y por una buena razón. Ofrecen un conjunto de pautas para resolver diversos problemas de software. La vida de los desarrolladores puede hacerse más accesible proporcionándoles diversos métodos generales de resolución de problemas.
Hoy en día existen varios algoritmos de programación, por lo que los ingenieros y desarrolladores de software deben ser conscientes de lo que hay disponible y de cuándo es mejor utilizarlo. Un buen algoritmo determinará cómo llevar a cabo una tarea o abordar un reto de la forma más rápida y con el mayor ahorro de memoria posible.
Algoritmo de clasificación
Los algoritmos de ordenación son un conjunto de instrucciones que toman una matriz o lista como entrada y ordenan los elementos en un orden específico.
Las ordenaciones suelen ser numéricas o alfabéticas (o lexicográficas) y pueden ser ascendentes (A-Z, 0-9) o descendentes (Z-A, 9-0). Dado que pueden reducir regularmente la complejidad de un problema, los algoritmos de ordenación son excepcionalmente importantes en informática. Estos algoritmos tienen aplicaciones directas en algoritmos de búsqueda, algoritmos de bases de datos, métodos de divide y vencerás, algoritmos de estructuras de datos y muchos más. A la hora de elegir un algoritmo de ordenación, hay que plantearse algunas preguntas: ¿Qué tamaño tiene la colección que se va a ordenar? ¿Cuánta memoria hay disponible? ¿Es necesario que la colección crezca?
Las respuestas a estas preguntas pueden determinar qué algoritmo va a funcionar mejor en cada circunstancia. Algunos algoritmos como la ordenación por fusión pueden necesitar mucho espacio o memoria para ejecutarse, mientras que la ordenación por inserción no siempre es la más rápida, pero no requiere muchos recursos para ejecutarse.
Algunos de los algoritmos de clasificación más comunes son:
- Clasificación por selección
- Clasificación por burbujas
- Clasificación por inserción
- Ordenar por fusión
- Clasificación rápida
- Clasificación en pilas
- Clasificación por recuento
- Clasificación Radix
- Clasificación por cubos
Algoritmo de búsqueda
A la hora de buscar información, la diferencia entre una aplicación rápida y otra más lenta radica en el uso preciso del algoritmo de búsqueda. Los algoritmos de búsqueda pueden ser un paso básico y principal en la informática que se realiza mediante un método paso a paso para encontrar un dato concreto entre un recogida de datos.
Todos los algoritmos de búsqueda utilizan una clave de búsqueda para completar el procedimiento. Y se espera que devuelvan un estado de éxito o fracaso (en valor booleano verdadero o falso). En informática, existen varios tipos de algoritmos de búsqueda, y la forma en que se utilizan decide el rendimiento y la eficacia de los datos disponibles (la forma en que se utilizan los datos). Estos algoritmos se clasifican en 2 categorías según su tipo de operaciones de búsqueda. Y son:
Búsqueda secuencial
En este caso, la lista o matriz se recorre secuencialmente y se comprueba cada elemento. Por ejemplo: Búsqueda lineal Búsqueda por intervalos. Estos algoritmos están diseñados específicamente para buscar en estructuras de datos ordenadas. Este tipo de algoritmos de búsqueda son más eficaces que el método de búsqueda lineal, ya que se dirigen repetidamente al centro de la estructura de búsqueda y dividen el espacio de búsqueda en 2 mitades. Por ejemplo: Búsqueda binaria. Estos son algunos tipos de algoritmos de búsqueda:
- Búsqueda lineal
- Búsqueda binaria
- Saltar búsqueda
- Búsqueda por interpolación
- Búsqueda exponencial
- Sublist Search (Búsqueda de una lista enlazada en otra lista)
- Búsqueda Fibonacci
- La búsqueda binaria ubicua
Programación dinámica
La Programación Dinámica es una optimización sobre la recursividad simple. Siempre que veamos una solución recursiva que tenga llamadas repetidas para las mismas entradas, podemos optimizarla utilizando la Programación Dinámica. La idea es almacenar los resultados de los subproblemas para no tener que volver a calcularlos cuando sea necesario. Esta sencilla optimización reduce la complejidad temporal de exponencial a polinómica. Aquí, problemas de optimización significa que cuando estamos tratando de encontrar la solución mínima o máxima de un problema. La programación dinámica garantiza encontrar la solución óptima de un problema en caso de que la solución exista.
La definición de programación dinámica dice que es un procedimiento para resolver un problema complejo dividiéndolo primero en una colección de subproblemas menos complejos, resolviendo cada subproblema una sola vez y almacenando después sus soluciones para evitar cálculos repetitivos.
La Programación Dinámica sigue una serie de pasos:
- Descompone un problema complejo y de mayor envergadura en subproblemas más sencillos.
- Encuentra la mejor solución para los subproblemas
- Guarda los resultados de los subproblemas, lo que se conoce como memorización
- Los reutiliza para que el mismo subproblema se calcule más de una vez
- Por último, calcula el resultado del problema complejo
Algoritmo de recursión
Un algoritmo recursivo se llama a sí mismo con valores de entrada más pequeños y devuelve el resultado para la entrada actual realizando operaciones fundamentales sobre el valor devuelto para la información más pequeña. Si un problema puede resolverse aplicando soluciones a versiones más pequeñas del mismo problema, y las versiones más pequeñas se reducen a instancias fácilmente resolubles, en ese momento, el problema puede resolverse utilizando un algoritmo recursivo. Para construir un algoritmo recursivo, dividiremos el enunciado del problema en dos partes. La primera es el caso base, y la segunda es el paso recursivo.
Caso Base: Se trata de un problema consistente en una función recursiva terminada en condición. Este caso base evalúa el resultado cuando se cumple una situación dada.
Paso recursivo: Calcula el resultado haciendo llamadas recursivas al mismo trabajo pero con las entradas disminuidas en tamaño o complejidad.
También existen diversos tipos de recursiones:
Recursión directa: Una función se denomina recursiva natural si se llama a sí misma repetidamente en su cuerpo de función.
Recursividad indirecta: Tipo de recursión en la que la función se llama a sí misma a través de otra función.
Divide y vencerás
Esta técnica puede dividirse en las tres partes siguientes:
Divide: Esto incluye separar el problema en subproblemas más pequeños.
Conquista: Desentraña subproblemas llamando recursivamente hasta resolverlos.
Los subproblemas para inducir la solución final del problema completo.
Algunas de las ventajas del algoritmo Divide y vencerás:
- Un problema complejo puede resolverse fácilmente
- Reduce la complejidad temporal del problema
- Divide el problema en subproblemas para poder resolverlo en paralelo, garantizando el multiprocesamiento.
- No ocupa mucha memoria caché
