¿Cuáles son las razones para aprender diferentes algoritmos / estructuras de datos que tienen el mismo propósito?

Me he estado preguntando acerca de esta pregunta desde que era estudiante de pregrado. Es una pregunta general, pero elaboraré con ejemplos a continuación.

He visto muchos algoritmos, por ejemplo, para problemas de flujo máximo, conozco alrededor de 3 algoritmos que pueden resolver el problema: Ford-Fulkerson, Edmonds-Karp y Dinic, con Dinic con la mejor complejidad.

Para estructuras de datos, por ejemplo, montones, hay montones binarios, montones binomiales y montones de Fibonacci, con el montón de Fibonacci que tiene la mejor complejidad general.

Lo que me mantiene confuso es: ¿hay alguna razón por la que necesitemos conocerlos a todos? ¿Por qué no simplemente aprender y familiarizarse con la mejor complejidad?

Sé que es mejor si los conocemos a todos, solo quiero saber si hay razones "más válidas", como algunos problemas / algoritmos que solo pueden resolverse usando A pero no B , etc.

Hay un libro de texto en espera de ser escrito en algún momento, con el título de trabajo Estructuras de datos, algoritmos y compensaciones . Casi todos los algoritmos o estructuras de datos que probablemente aprenderá a nivel de pregrado tienen alguna característica que lo hace mejor para algunas aplicaciones que para otras.

Tomemos la clasificación como un ejemplo, ya que todos están familiarizados con los algoritmos de clasificación estándar.

En primer lugar, la complejidad no es la única preocupación. En la práctica, los factores constantes son importantes, por lo que (por ejemplo) la ordenación rápida tiende a usarse más que la ordenación en montón aunque la ordenación rápida tiene una terrible complejidad en el peor de los casos.

En segundo lugar, siempre existe la posibilidad de que te encuentres en una situación en la que estás programando bajo restricciones extrañas. Una vez tuve que hacer una extracción cuantílica de una colección de muestras de tamaño modesto (más o menos 1000) lo más rápido posible, pero estaba en un pequeño microcontrolador que tenía muy poca memoria de lectura y escritura de repuesto, por lo que descartó la mayoría de ordenar algoritmos. La ordenación de Shell fue la mejor compensación, ya que era subcuadrática y no requería memoria adicional.$O(n \log n)$

En otros casos, las ideas de un algoritmo o estructura de datos podrían ser aplicables a un problema de propósito especial. El ordenamiento de burbujas parece ser siempre más lento que el de inserción en hardware real, pero la idea de realizar un pase de burbuja es a veces exactamente lo que necesita.

Considere, por ejemplo, algún tipo de visualización en 3D o videojuego en una tarjeta de video moderna, donde le gustaría dibujar objetos en orden desde el más cercano a la cámara hasta el más alejado de la cámara por razones de rendimiento, pero Si no obtiene el pedido exacto, el hardware se encargará de ello. Si se está moviendo por el entorno 3D, el orden relativo de los objetos no cambiará mucho entre fotogramas, por lo que realizar una pasada de burbuja en cada fotograma podría ser una compensación razonable. (El motor Source de Valve hace esto para los efectos de partículas).

Hay persistencia, concurrencia, localidad de caché, escalabilidad en un clúster / nube y una serie de otras posibles razones por las cuales una estructura de datos o algoritmo puede ser más apropiado que otro, incluso dada la misma complejidad computacional para las operaciones que le interesan.

Dicho esto, eso no significa que deba memorizar un montón de algoritmos y estructuras de datos por si acaso. La mayor parte de la batalla es darse cuenta de que hay una compensación para ser explotada en primer lugar, y saber dónde buscar si cree que podría haber algo apropiado.

Además del hecho de que hay miles de medidas de costos (tiempo de ejecución, uso de memoria, errores de caché, predicciones erróneas de ramas, complejidad de implementación, factibilidad de verificación ...) en miles de modelos de máquinas (TM, RAM, PRAM, ...) , el promedio frente al peor de los casos, así como las consideraciones de amortización para sopesar entre sí, a menudo también hay diferencias funcionales más allá del alcance de la especificación básica del libro de texto.

Algunos ejemplos:

• Mergesort es estable donde Quicksort no lo es.
• Los árboles de búsqueda binarios le dan una iteración en orden, las tablas hash no.
• Bellman-Ford puede lidiar con pesos de borde negativos, Dijkstra no puede.

También hay que hacer consideraciones didácticas :

• ¿Qué tan fácil es entender una solución más complicada antes que las más simples? (Árboles AVL (y su análisis) sin BST; Dinic sin Ford-Fulkerson; ...)
• ¿Ves los mismos principios y patrones cuando estás expuesto a una sola solución por problema en comparación con estar expuesto a muchas soluciones?
• ¿La exposición a una sola solución por problema proporciona suficiente capacitación (hacia el dominio)?
• ¿Debería saber la amplitud de las soluciones que se han encontrado (para evitar que reinvente la rueda una y otra vez)?
• Cuando se expone a una sola solución por problema, ¿comprenderá otras soluciones que encuentre en la naturaleza (por ejemplo, en una biblioteca de programación del mundo real)?

1. Esto es algo que vemos mucho de los tipos de programadores que no tienen una rica caja de herramientas CS a su disposición.

En el mundo real , en algún momento es probable que esté trabajando en un software que ha sido escrito por un equipo de otras personas. ¡Parte de este software habrá sido escrito antes de que nacieras!

Para comprender los algoritmos / estructuras de datos que se utilizan, es muy útil conocer una gran cantidad de algoritmos / estructuras de datos, incluidas las opciones que ya no se consideran "estado del arte".

También tendrá que trabajar en algoritmos que no son estándar y que solo se usan en la aplicación en la que está trabajando. Cuando tenga que mejorar estos algoritmos, encontrará que su cerebro se ha llenado de métodos útiles para mejorar los algoritmos, ya que ha estudiado cómo otras personas han mejorado los algoritmos.

Esto es lo que diferencia a alguien que ha estudiado informática aparte de alguien que acaba de aprender a programar. En la mayoría de los trabajos en los que he trabajado, ha habido un tiempo en que al estudiar ciencias de la computación pude resolver un problema que un programador "aprendido de los libros" no pudo, pero el 95% de las veces descubrí que haber estudiado ciencias de la computación no me daba ninguna ventaja. sobre otros programadores experimentados .

Muchas personas han mencionado con razón que a menudo no hay un mejor algoritmo, depende de la situación.

También existe la posibilidad de que algún día te encuentres con una situación desconocida. Cuantos más algoritmos conozca, más posibilidades tendrá de conocer uno que sea casi una solución que pueda usar como base.

Muchas respuestas geniales, creo que falta algo, aunque la respuesta de Raphael menciona esto de alguna manera.

La facilidad de implementación también es algo a tener en cuenta.
Eso generalmente no es un problema con los algoritmos de clasificación, porque la mayoría de las plataformas / lenguajes ya tienen uno implementado (y a menudo mejor que lo que podría hacer), pero es posible que no haya algoritmos más inusuales disponibles.
Dependiendo de su problema, es posible que no necesite el mejor algoritmo absoluto si el tiempo de implementación es de 1 día versus 2 semanas.