Las estrategias de diseño de algoritmos son técnicas utilizadas para modificar las ejecuciones y el rendimiento de algoritmos. Podemos medir estas modificaciones a través del análisis de algoritmos. Discutamos un ejemplo simple para ver la diferencia en eficiencia que podemos hacer a través de técnicas de diseño de algoritmos; Considere el algoritmo de búsqueda lineal , está buscando una clave en una matriz y luego devuelve su índice si existe o falla de lo contrario. ¡Está visitando toda la matriz para obtener ese índice de la clave! Por lo tanto, decimos que es de orden O (n) . En realidad, es la solución intuitiva para el problema de búsqueda, uno de los problemas fundamentales en informática. Sin embargo, si podemos pensar un poco más para encontrar mejores soluciones, podemos hacer lo siguiente: ¡Si la matriz está ordenada , podemos ignorar la mitad de la matriz a través del algoritmo de búsqueda binaria! e ignorando la mitad de la mitad restante en la segunda iteración del algoritmo y la mitad de los elementos restantes en las próximas iteraciones y así sucesivamente. La búsqueda binaria es un muy buen ejemplo de la técnica de diseño de divide y vencerás . ¡Solo visita una cantidad de elementos [math] log (n) [/ math] en la matriz! Por lo tanto, es de [matemáticas] O (log n) [/ matemáticas].
También hay más técnicas además de esta técnica, tales como:
- Inducción : un buen ejemplo es la versión recursiva del algoritmo para encontrar números de Fibonacci.
- Programación dinámica : se usa ampliamente en bioinformática y combinatoria y un buen ejemplo de ello es el algoritmo de subsecuencia común más largo.
- Algoritmos codiciosos : un muy buen ejemplo es el algoritmo Dijkstra para encontrar la ruta más corta desde un nodo específico en un gráfico.
Hay muchos libros que abordan estos temas, como Algoritmos: Técnicas de diseño y análisis, el conocido libro de Cormen y Algoritmos.
- ¿Cuál es el enfoque para encontrar un acuerdo que produzca el salario mínimo?
- Visión por computadora: las aplicaciones de Richard Szeliski ofrecen una buena (amorosa) montaña rusa a través de la historia de los algoritmos. ¿Cómo puedo usarlo mejor?
- ¿Qué son las estructuras de datos y los algoritmos en c ++?
- ¿Qué se entiende por 'profundidad' en DFS?
- ¿Por qué BFS no puede resolver todos los problemas de ruta más corta de una sola fuente?
También puede navegar por Internet para obtener tutoriales en línea.
