¿Hay alguna herramienta que pueda determinar realizar 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" ya que, por lo 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 ¿hay alguna complejidad de tiempo (y/o espacio)? Si es así, cuáles, si no, ¿por qué no? ¿Es inviable? ¿Imposible? ¿Alguien simplemente no ha llegado a eso?

Lo ideal sería que habría algo así como la complejidad general para la aplicación (definición diferente posible "n" s), así como para cada método en la aplicación

Editar: por lo que parece una solución exacta es imposible porque del Halting Problem, sin embargo, ¿es posible algún tipo de aproximación heurística? Me doy cuenta de que, para fines prácticos, un buen generador de perfiles dará mucha más información útil, pero parece ser un problema interesante.

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

Answer 1

Por desgracia, no es este problema llamado el Halting problem ...

Answer 2

No, esto no es posible, debido al problema de la parada.

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

Answer 3

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 algunas veces me han sorprendido cosas que, en mi opinión, tomaron mucho tiempo, y en realidad tomaron muy poco y viceversa. En el mundo de .NET, he usado ANTS y las herramientas JetBrains.

Answer 4

Unos thoughs:

ordenadores reales son aproximadamente máquinas de estados finitos deterministas, por lo que el problema de la parada no es en realidad una limitación práctica. Una limitación práctica es un algoritmo que toma más tiempo para ejecutarse de lo que te apetece 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 empleado. Luego trace una curva a través de los datos.

Analizar la complejidad del tiempo de los algoritmos puede ser bastante complicado, requiriendo algunos pasos creativos. (Véase, por ejemplo, análisis de quicksort). El problema está estrechamente relacionado con la demostración lógica del teorema y la verificación del programa. Podría ser factible construir una herramienta útil que permita la solución semiautomática de la complejidad, es decir, una herramienta que busque de forma sistemática soluciones dadas por un humano, pero ciertamente no es fácil.