En la vida de los programadores, los algoritmos y las estructuras de datos son el tema más importante si quieren salir al mundo de la programación y hacer algunos dólares. Hoy, veremos qué hacen y dónde se usan con ejemplos más simples. Esta lista se prepara teniendo en cuenta su uso en la programación competitiva y las prácticas de desarrollo actuales.

Algoritmos de ordenación

La ordenación es el concepto más estudiado en Ciencias de la Computación. La idea es organizar los elementos de una lista en un orden específico. Aunque todos los lenguajes de programación principales tienen bibliotecas de clasificación integradas, es útil si sabes cómo funcionan. Dependiendo de los requisitos, es posible que desee usar cualquiera de estos.

• Merge Sort
• Quick Sort
• Bucket Sort
• Heap Sort
• Conteo de Tipo

lo Más importante que uno debe saber cuándo y dónde usarlos. Algunos ejemplos donde puede encontrar la aplicación directa de técnicas de clasificación incluyen:

• Ordenar por precio, popularidad, etc. en sitios web de comercio electrónico

Algoritmos de búsqueda

Búsqueda binaria (en estructuras de datos lineales)

La búsqueda binaria se utiliza para realizar una búsqueda muy eficiente en conjuntos de datos ordenados. La complejidad temporal es O (log2N). La idea es dividir repetidamente por la mitad la parte de la lista que podría contener el elemento, hasta que lo reduzcamos a un elemento posible. Algunas aplicaciones son:

• Cuando busca un nombre de canción en una lista ordenada de canciones, realiza búsquedas binarias y coincidencias de cadenas para devolver rápidamente los resultados.
• Se utiliza para depurar en git a través de git bisect

Profundidad/Amplitud Primera búsqueda (en estructuras de datos de gráficos)

DFS y BFS son estructuras de datos de árbol / gráfico que atraviesan y buscan. No profundizaríamos en cómo funcionan los DFS / BFS, pero veremos cómo son diferentes a través de la siguiente animación.

Aplicaciones:

• Utilizadas por los motores de búsqueda para el rastreo web
• Utilizadas en inteligencia artificial para construir bots, por ejemplo, un bot de ajedrez
• Encontrando el camino más corto entre dos ciudades en un mapa y muchas otras aplicaciones similares

Hash

La búsqueda de Hash es actualmente la técnica más utilizada para encontrar datos apropiados por clave o ID. Accedemos a los datos por su índice. Anteriormente nos basábamos en la Clasificación + Búsqueda binaria para buscar el índice, mientras que ahora usamos hash.

La estructura de datos se denomina Mapa de Hash o Tabla de Hash o Diccionario que asigna claves a valores de manera eficiente. Podemos realizar búsquedas de valores usando claves. La idea es usar una función hash adecuada que haga la asignación de valores key ->. Elegir una buena función hash depende del escenario.

Aplicaciones:

• En enrutadores, para almacenar la dirección IP – > Par de rutas para mecanismos de enrutamiento
• Para realizar la comprobación de si un valor ya existe en una lista. La búsqueda lineal sería costosa. También podemos utilizar la estructura de datos de conjunto para esta operación.

Programación dinámica

La programación dinámica (DP) es un método para resolver un problema complejo al dividirlo en subproblemas más simples. Resolvemos los subproblemas, recordamos sus resultados y usándolos nos abrimos camino para resolver el problema complejo, rápidamente.

*escribe «1+1+1+1+1+1+1+1 =» en una hoja de papel* ¿Qué es eso igual?
*contar* Ocho!* escribe otro «1+» a la izquierda* ¿Qué pasa con eso?¡rápido, nueve!¿Cómo sabías que eran nueve tan rápido?
Acabas de añadir uno más Para no tener que contar porque recordaste que había ocho! La programación dinámica es solo una forma elegante de decir ‘recordar cosas para ahorrar tiempo más tarde’

Aplicaciones:

• Hay muchos algoritmos y aplicaciones de DP, pero nombraría uno y te sorprendería, el método Duckworth-Lewis en cricket.

Exponenciación por cuadratura

Digamos que desea calcular 232. Normalmente repetiríamos 32 veces y encontraríamos el resultado. ¿Y si te dijera que se puede hacer en 5 iteraciones?La exponenciación por cuadratura o exponenciación binaria es un método general para el cálculo rápido de grandes potencias enteras positivas de un número en O (log2N). No solo esto, el método también se utiliza para el cálculo de potencias de polinomios y matrices cuadradas.

Aplicación:

• El cálculo de grandes potencias de un número se requiere principalmente en el cifrado RSA. RSA también utiliza aritmética modular junto con exponenciación binaria.

Coincidencia y análisis de cadenas

Coincidencia/búsqueda de patrones es uno de los problemas más importantes en Informática. Ha habido mucha investigación sobre el tema, pero solo incluiremos dos necesidades básicas para cualquier programador.

Algoritmo KMP (Coincidencia de cadenas)

El algoritmo Knuth-Morris-Pratt se utiliza en los casos en que tenemos que coincidir con un patrón corto en una cadena larga. Por ejemplo, cuando Ctrl + F una palabra clave en un documento, realizamos coincidencias de patrones en todo el documento.

Expresión regular (Análisis de cadenas)

Muchas veces tenemos que validar una cadena analizando una restricción predefinida. Se usa mucho en el desarrollo web para analizar y emparejar URL.

Algoritmos de prueba de primalidad

Existen formas deterministas y probabilísticas de determinar si un número dado es primo o no. Veremos formas deterministas y probabilísticas (no deterministas).

Tamiz de Eratóstenes (determinista)

Si tenemos cierto límite en el rango de números, digamos determinar todos los primos dentro del rango de 100 a 1000, entonces el tamiz es un camino a seguir. La longitud de rango es un factor crucial, porque tenemos que asignar cierta cantidad de memoria de acuerdo con el rango.

Para cualquier número n, probando de forma incremental hasta sqrt(n) (determinista)

En caso de que desee verificar algunos números que están dispersos en un rango largo (por ejemplo, del 1 al 1012), Sieve no podrá asignar suficiente memoria. Puede verificar cada número n recorriendo solo hasta sqrt (n) y realizar una comprobación de divisibilidad en n.

Prueba de primalidad de Fermat y prueba de primalidad de Miller–Rabin (ambas no son deterministas)

Ambas son pruebas de compositividad. Si se demuestra que un número es compuesto, entonces seguro que no es un número primo. Miller-Rabin es más sofisticado que el de Fermat. De hecho, Miller-Rabin también tiene una variante determinista, pero luego es un juego de intercambio entre la complejidad del tiempo y la precisión del algoritmo.

Aplicación:

• El uso más importante de números primos es en criptografía. Más precisamente, se utilizan en cifrado y descifrado en algoritmo RSA, que fue la primera implementación de Criptosistemas de Clave Pública
• Otro uso es en funciones Hash utilizadas en tablas Hash