¿Hay alguna herramienta que pueda determinar el análisis de código para la complejidad de Big-O?

Question

No he visto nada por ahí, y sospecho la dificultad de definir " n " dado que, en general, para analizar una función compleja, habría más de una o dos variables para definir.

Existen herramientas de análisis para la complejidad ciclomática, pero ¿existen para la complejidad del tiempo (y / o el espacio)? Si es así, ¿cuáles, si no, por qué no? ¿Es inviable? ¿Imposible? ¿Alguien simplemente no lo ha conseguido?

Idealmente, habría algo así como la complejidad general de la aplicación (definiendo diferentes 'n' posibles), así como para cada método en la aplicación

Editar: por lo tanto, parece que una solución exacta es imposible debido al Problema de detención , ¿Es posible algún tipo de aproximación heurística? Me doy cuenta de que, a efectos prácticos, un buen generador de perfiles proporcionará mucha más información útil, pero parece un problema interesante.

Además, ¿qué tal uno que calcula para un determinado subconjunto de programas?

Answer 1

Desafortunadamente, existe este problema llamado Problema de detención ...

Answer 2

No, esto no es posible debido al problema de detención.

Si desea hacer esto para mejorar sus aplicaciones, puede considerar la creación de perfiles. Le permitiría determinar qué es lo que realmente lleva más tiempo. De esta manera, no pasa tiempo optimizando un algoritmo O (n ^ 3) que solo se ejecuta en pequeños conjuntos de datos.

Answer 3

Algunas reflexiones:

Las computadoras reales son máquinas de estado finito aproximadamente deterministas, por lo que el problema de detención no es en realidad una limitación práctica. Una limitación práctica es un algoritmo que tarda más tiempo en ejecutarse de lo que parece esperar, descartando cualquier método de análisis de fuerza bruta.

Para tener una idea aproximada de la complejidad de un algoritmo, siempre puede ejecutarlo en un conjunto de entradas aleatorias y medir el tiempo necesario. Luego, trace una curva a través de los datos.

Analizar la complejidad temporal de los algoritmos puede ser bastante complicado, ya que requiere algunos pasos creativos. (Ver, por ejemplo, análisis de clasificación rápida). El problema está estrechamente relacionado con la prueba del teorema lógico y la verificación del programa. Podría ser factible construir una herramienta útil que permita una solución semiautomática de complejidad, es decir, una herramienta que busque sistemáticamente soluciones dadas por un humano, pero ciertamente no es fácil.

Answer 4

Nunca he visto una herramienta para hacer esto, pero utilizamos herramientas de creación de perfiles para tener una mejor idea de dónde están los cuellos de botella. No siempre es obvio y me han sorprendido varias veces las cosas que pensé que tomaron mucho tiempo, en realidad tomaron muy poco y viceversa. En el mundo .NET, he usado ANTS y el < a href = "http://www.jetbrains.com/profiler/" rel = "nofollow noreferrer"> herramientas JetBrains .