Para la mayoría de los problemas, calcular el tiempo de ejecución asintótico es bastante difícil. Pero para problemas más simples, con frecuencia se ha realizado mucha más investigación.
Por ejemplo, la clasificación de una matriz con elementos [math] n [/ math] es conocida por tomar comparaciones [math] \ Theta (n \ log n) [/ math], y varios algoritmos han logrado este límite asintóticamente.
Pero quicksort continúa siendo estudiado activamente. Ha habido múltiples análisis en los últimos años analizando el efecto del uso de dos o tres pivotes en lugar de uno solo.
- ¿Qué programa universitario de ciencias de la computación hace que sus estudiantes escriban más código?
- ¿Qué tan ocupados están los candidatos a la facultad de ciencias de la computación durante las temporadas de reclutamiento? ¿Es un buen momento para pedirles oportunidades de investigación?
- ¿La fotogrametría hará que la escultura digital sea obsoleta?
- ¿Cuánto más rápido es una computadora cuántica que una computadora tradicional? ¿Cómo se realiza el direccionamiento de memoria?
- Si empiezo a leer artículos científicos, ¿cuáles son los documentos que deben leerse sobre la conversión de 'discurso a texto'?
Del mismo modo, el algoritmo de Dijkstra para calcular las rutas más cortas se conoce desde hace décadas. Pero todavía hay muchas otras preguntas interesantes que se han estudiado. (Si está interesado en el estado de cualquiera de estos, me complace ayudarlo a encontrar referencias).
- ¿Podemos encontrar las k rutas más cortas entre dos nodos, para algún entero fijo k?
- ¿Podemos equilibrar múltiples pesos uno contra el otro?
- ¿Podemos paralelizar el problema?
- ¿Podemos usar la heurística para acelerar nuestro cálculo?
- ¿Podemos preprocesar un gráfico para responder consultas de ruta más cortas aún más rápido?
Y eso está fuera de mi cabeza. A pesar de la impresión que puede tener de los libros de texto de algoritmos, los problemas algorítmicos prácticamente nunca se resuelven definitivamente.
