¿Existe un método para el análisis automático de algoritmos en tiempo de ejecución?

Me pregunto, ¿hay algún método para el análisis automático de tiempo de ejecución que funcione al menos en un subconjunto relevante de algoritmos (algoritmos que se pueden analizar)?

Busqué en Google "Análisis de algoritmo automático" que me dio esto, pero es demasiado complicado. Solo quiero un ejemplo simple en psuedocode que pueda entender. Podría ser demasiado específico, pero pensé que valía la pena intentarlo.

La herramienta COSTA hace exactamente esto, aunque falla en muchos casos, como puede imaginar, debido a problemas de computabilidad . Hay muchos documentos sobre esto; El análisis de costos de Java Bytecode por E. Albert, P. Arenas, S. Genaim, G. Puebla, D. Zanardini es un buen punto de partida.

El enfoque adoptado es inferir una recurrencia en tiempo de ejecución del código Javabyte, y convertirlo a una forma cerrada. La herramienta también calcula los límites de uso del espacio.

Ningún algoritmo puede decidir si un algoritmo dado alguna vez se detiene o no, por lo que, en particular, ningún algoritmo puede analizar estrictamente la complejidad de un algoritmo dado.

Conozco un enfoque para el análisis de casos promedio (semi) automatizado, a saber, MaLiJAn ¹. Se parece mucho al tipo de análisis que Knuth usa en TAoCP. La idea central es

• modelar el programa (flujo) como Markov Chain,
• $n$
• $n$
• use álgebra computacional para obtener el costo promedio (wrt estas funciones).

Tenga en cuenta que solo las medidas de costo aditivas (por ejemplo, comparaciones, "tiempo") funcionan y solo el valor esperado es preciso (suponiendo funciones de probabilidad perfectas), no se pueden derivar momentos más altos.

Todos los pasos, excepto la extrapolación, son rigurosos [2] y se ha demostrado que el método reproduce resultados bien conocidos con alta precisión, dada la entrada de muestras aleatorias adecuadas, por supuesto. Si bien no hay pruebas ni garantías de aproximación de los resultados (el paso de extrapolación es, hasta ahora, puramente heurístico), los resultados obtenidos con la herramienta sirven para experimentar con algoritmos difíciles de analizar y formular hipótesis [3,4].

1. Divulgación completa: fui miembro de este grupo de investigación y participé en el desarrollo de la herramienta.
2. Análisis de máxima verosimilitud de algoritmos y estructuras de datos por U. Laube y M. Nebel (2010) [ preprint ]
3. Ingeniería del Quicksort Dual Pivot de Java 7 usando MaLiJAn por S. Wild et al (2012) [ preprint ]
4. Análisis de máxima verosimilitud del método Ford – Fulkerson en gráficos especiales por U. Laube und M. Nebel (2015) [ preprint ]

Por supuesto, como señaló Yuval Filmus, uno no debería esperar una solución general a tales problemas. Pero como suele ser el caso, se pueden encontrar soluciones para subconjuntos interesantes del caso general.

De ninguna manera soy un experto, o incluso un gran conocimiento en esta área, por lo que sé de algún trabajo de este tipo. Se trata del análisis automático de complejidad promedio, y el trabajo fue realizado por Philippe Flajolet y sus colegas.

$\lambda\acute\upsilon\omega$

Un artículo que encontré en la web es uno de 1990: análisis automático de algoritmos de casos promedio por Philippe Flajolet, Paul Zimmermann y Bruno Salvy .

Esperaría que documentos posteriores hayan extendido este trabajo, pero realmente no lo sé. El trabajo fue muy citado, y buscarlo en la web debería generar un trabajo más reciente sobre el mismo tema.

Ahora, me temo que el trabajo de Flajolet y sus colegas fue muy matemático, y no esperaría mucha lectura fácil.