Como estamos hablando de una lista de los 10 principales, me imagino que te refieres al nivel más introductorio. Aquí hay algunos buenos. Esta lista obviamente no está completa; Estos son solo algunos de los algoritmos más comunes encontrados, sin ningún orden en particular.
1. Búsqueda binaria: para cualquier situación en la que no sabe cuál es la respuesta, pero puede adivinar una respuesta y luego determinar si era demasiado baja o demasiado alta.
2. Búsqueda de amplitud primero (BFS): se utiliza para encontrar rutas más cortas en un gráfico no ponderado. También se puede usar para problemas de conteo de componentes conectados o conectividad de gráficos, aunque para estos problemas DFS también es una opción. Es más fácil de implementar que DFS si no implementa DFS de forma recursiva (lo que a veces no desea hacer por temor a exceder el límite de memoria de la pila).
- Cómo comenzar a practicar algoritmos para la codificación
- ¿Qué algoritmos se usan en los sistemas de recomendación?
- Como estudiante de primer año de una sucursal que no es CS en un IIT, ¿cómo domino las estructuras de datos, los algoritmos y el aprendizaje automático por mi cuenta?
- ¿Cuál es la solución a la siguiente relación de recurrencia: [matemáticas] T (n) = 3T (n-1) - 7T (n-2) + 9T (n-3) [/ matemáticas], con las siguientes condiciones iniciales: [ matemática] T (0) = 1 [/ matemática], [matemática] T (1) = 6 [/ matemática], [matemática] T (2) = 7 [/ matemática]. ¿Qué es una expresión para [math] T (n) [/ math] de modo que no haya términos [math] T (i (\ frac {n} {j}) ^ {k}) [/ math] a la derecha ¿lado?
- Cómo llegar a la lógica para construir un método de impresión inversa que imprima los nodos en una lista vinculada usando un enfoque recursivo usando Java
3. Búsqueda de profundidad primero (DFS): se puede utilizar para encontrar un ciclo en un gráfico, para hacer una clasificación topológica o para encontrar puentes / puntos de articulación, entre otras cosas.
4. Algoritmo de Dijkstra: encuentra la ruta más corta entre dos vértices en un gráfico ponderado. Muchos problemas tienen pesos (distancias, costos) en el gráfico y, por lo tanto, no se pueden resolver solo con BFS.
5. Caminar con puntero: idea general de tener dos punteros en una matriz y moverlos en tándem.
Ejemplo: dado un conjunto de enteros positivos, encuentre el subconjunto más grande donde el máximo es menos del doble del mínimo. Te darás cuenta de que esto es lo mismo que ordenar la entrada y luego pedir el subconjunto más grande donde se cumple la condición. ¿Cómo encontrarlo con eficacia? Cree dos punteros en la matriz que represente los límites inferior y superior. Cada vez que mueva el puntero del límite inferior, avance el puntero del límite superior desde su posición anterior tanto como pueda sin violar los criterios. Dado que ambos punteros solo avanzan, hay como máximo 2N avances de puntero (donde N es el tamaño de la matriz) y el algoritmo solo requiere tiempo O (n) además del costo de la clasificación.
6. Recorridos de árboles: muchos problemas básicos sobre los árboles se reducen a atravesar el árbol en un orden adecuado y devolver los resultados de los cálculos de los subárboles a los árboles primarios a medida que avanza. Ejemplo súper simple: suma los campos de valor en todos los nodos en un árbol de búsqueda binario.
7. Recursión y retroceso: esta es una técnica general, no un algoritmo. Cuando su algoritmo necesite tomar una decisión, tome una decisión arbitraria, y cuando no pueda llegar a una solución, retroceda en sus elecciones hechas anteriormente y pruebe otras diferentes.
8. Recursión con la memorización (programación dinámica de arriba hacia abajo): nuevamente no es un algoritmo, sino más bien una técnica general. Cuando escribe una fórmula recursiva como en el punto 7 anterior, pero en el transcurso de la recursividad, se resuelven casos idénticos varias veces, puede almacenar en caché las respuestas a los casos calculados previamente para evitar volver a calcularlos. Puede almacenar respuestas a casos calculados previamente con cualquier tipo de estructura de mapa (por ejemplo, tabla hash, BST equilibrado).
9. Programación dinámica ascendente: tampoco un algoritmo sino una técnica. A veces, resolver casos en un orden en particular le permite evitar la recursión por completo, porque el resultado de cada llamada recursiva que haría ya se ha memorizado para el momento en que lo haría, por lo que puede acceder al resultado que necesita desde una matriz o mapa. Esta técnica a veces conduce a un código más simple y factores constantes más bajos que si hubiera usado el método en 8.
10. Árboles de segmentos: esta es una estructura de datos que se utiliza en una amplia variedad de problemas. En general, se usa para responder preguntas como “Dada una matriz A y un conjunto de consultas, cada una de las cuales consta de dos índices i y j en A, cuál es el valor, para cada consulta, de la propiedad X para A [i … j]? ” Un ejemplo de la propiedad X sería la suma de la submatriz o el mínimo de la submatriz. Un árbol de segmentos puede resolver problemas como este de manera eficiente incluso en presencia de actualizaciones en la matriz subyacente.
