Recopilatorio de algoritmos básicos, con un enlace a sus pseudocódigos y código fuente en diferentes lenguajes. También se incluyen algunos resultados que pueden ser útiles.
Encuentra el máximo común divisor entre dos números.
Encuentra el máximo común divisor junto a los coeficientes de Bézout. Es más largo de implementar, así que si no se necesitan los coeficientes es más fácil hacer el normal.
Permite encontrar la lista de todos los primos por debajo de un natural fijo.
Algoritmo para factorizar enteros de forma más rápida que a fuerza bruta.
Algoritmo para factorizar enteros, es el algoritmo más rápido para números que tengan cien dígitos o menos. Es bastante complicado de implementar.
Algoritmo para encontrar un camino de coste mínimo que vaya de un nodo N_1 a otro nodo N_2 en un grafo G. Hace falta una heurística h(n) que estime cual es el coste mínimo desde n hasta el objetivo, N_2.
Igual que el A*, este algoritmo encuentra un camino de coste mínimo que vaya de un nodo N_1 a otro nodo N_2 en un grafo G, pero esta vez no hace falta una función heurística h. De hecho, este algoritmo no es más que un A* donde la heurística es la función 0.
Encuentra el árbol generador minimal de un grafo G.
Encuentra la longitud del camino más corto entre todos los posibles pares de vértices en un grafo G.
Algoritmo de ordenación que es un ejemplo de estructura de divides y vencerás.
Algoritmo de ordenación, es uno de los más eficientes en media.
Encuentra un movimiento para el jugador actual que maximiza su ganancia suponiendo que su oponente jugará perfecto.
Mejora del minimax. Encuentra también un movimiento para el jugador actual que maximiza la ganancia suponiendo movimientos perfectos, pero reduce el árbol de búsqueda eliminando ramas innecesarias.
Este teorema permite hacer algoritmos para obtener la jugada perfecta en juegos imparciales (a no ser que sean juegos muy específicos o que el problema esté diseñado para usar este teorema, lo usual es que un juego no sea imparcial). La idea es que este teorema relaciona cualquier juego imparcial con un juego del Nim de forma constructiva, y este tiene un algoritmo rápido para jugar de forma perfecta.
Por añadir contexto, se necesita en la mitad de problemas de la sección Game Theory de Hackerrank.
Factoriza una matriz como producto de una triangular inferior por otra triangular superior. Una vez descompuesta, permite resolver un sistema de ecuaciones lineales con esa matriz de coeficientes.
Fórmula que permite saber en qué día de la semana cayó una fecha solo con el mes, día y año. La pongo en la lista porque, sin esto, este tipo de ejercicios son bastante complicados. Basta con recordar que existe.
Algoritmo que resuelve M preguntas sobre intervalos de un vector de N elementos en tiempo O(N*√N). Es necesario para algunos problemas de Hackerrank.