Foro de elhacker.net

Programación => Programación General => Mensaje iniciado por: JonaLamper en 15 Diciembre 2015, 18:44 pm



Título: Complejidad de un programa
Publicado por: JonaLamper en 15 Diciembre 2015, 18:44 pm
En primer lugar, no sé dónde debería ir esto, así que lo pongo aquí que sé que será leído en pocos minutos.

Quería saber si alguien conoce alguna página web donde tu subas un programa (algoritmo) y le puedas meter unos determinados valores para que, cuando finalice, te diga el coste que tiene tu algoritmo (y si te lo clasifica en un orden de complejidad sería como alcanzar un estado Zen de felicidad).

Gracias  ;D


Título: Re: Complejidad de un programa
Publicado por: Oblivi0n en 15 Diciembre 2015, 19:26 pm
Lo dudo mucho, aún así hacerlo a mano no es un proceso muy complejo.

Si no tienes el código, haz unas graficas en excel con las funcion f(n) = log n, f(n) = n* log n, f(n) = n, f(n) = n^2 * log n, f(n) = n^2 y sucesivas, mide tiempo con cada vez mas valores y mira a que curva se aproxima mas


Título: Re: Complejidad de un programa
Publicado por: engel lex en 15 Diciembre 2015, 19:52 pm
recuerda que si haces eso mide solo el tiempo del algoritmo, no de todo el programa... si no tomarás mucho tiempo de más


Título: Re: Complejidad de un programa
Publicado por: ivancea96 en 17 Diciembre 2015, 16:16 pm
Había visto un juego en Condingame que pedía eso, dado un set N-Tiempo, sacar el tipo de complejidad. Si buscas por CondinGame alguien que lo haya hecho, y te comenta su algoritmo, puedes hacer lo que pides tú mismo xd

Me has dado ganas de intentar ese reto jaja


Título: Re: Complejidad de un programa
Publicado por: Eleкtro en 17 Diciembre 2015, 16:54 pm
Antes de nada, ¿a quien se le ocurre formular una pregunta de programación sin especificar el lenguaje?, es algo que no soporto :¬¬, jeje.



Asumiré que por "coste" te estás intentando referir a la complejidad ciclomática (y no al intervalo de tiempo de ejecución que toma el algoritmo en cuestión para acabar):
  • Cyclomatic Complexity - Wikipedia (https://en.wikipedia.org/wiki/Cyclomatic_complexity)

Si, existen formulas para calcular la complejidad de unidades de código o Code units,
además, dependiendo del lenguaje que sea también podrás encontrar ciertas herramientas de escritorio e incluso desde la propia IDE que utilices.

Por ejemplo en la plataforma .Net (VB, C#, etc), en la IDE Visual Studio es tan sencillo como utilizar la opción "Calculate Code Metrics", esto generará un sofisticado informe completo sobre la complejidad ciclomática de la aplicación, y de todos sus miembros (métodos, funciones, classes, etc), así como otros factores como la cantidad de lineas de código, etc:

(http://i.imgur.com/K0QyXqu.png)

Una alternativa para .Net sería utilizar la herramienta de refactorización Telerik JustCode que se integra en Visual Studio y mide la complejidad de cada método en tiempo de diseño.
  • JustCode - Telerik (http://www.telerik.com/products/justcode.aspx)

En otros lenguajes desconozco que herramientas habrá, pero realizando una búsqueda en google veo que para la IDE Eclipse, la cual soporta varios lenguajes, hay un plugin llamado "Metrics":
  • Eclipse Metrics plugin - Sourceforge (http://sourceforge.net/projects/metrics/)

Te dejo algo de información sobre la fórmula, por si no encuentras herramientas automatizadas:
  • Cyclomatic Complexity - TutorialsPoint (http://www.tutorialspoint.com/software_testing_dictionary/cyclomatic_complexity.htm)
  • Cyclomatic Complexity - Guru99 (http://www.guru99.com/cyclomatic-complexity.html)

Saludos


Título: Re: Complejidad de un programa
Publicado por: DarK_FirefoX en 17 Diciembre 2015, 18:03 pm
En caso de que no te refieras a lo que menciona @Eleкtro:

Asumiré que por "coste" te estás intentando referir a la complejidad ciclomática (y no al intervalo de tiempo de ejecución que toma el algoritmo en cuestión para acabar):
  • Cyclomatic Complexity - Wikipedia (https://en.wikipedia.org/wiki/Cyclomatic_complexity)

Suponiendo que te refieres a Complejidad Temporal, te recomiendo que leas esto y después investiges más sobre el tema, pues no se si exista una aplicación como la que pides.

https://en.wikipedia.org/wiki/Time_complexity

Salu2s

PD: De cualquier manera, aclara mejor lo que pides.