[bcn-pm] Complejidad de algoritmos
José Luis Pérez Diez
jluisaescomposlinux.org
Div Jun 15 03:27:28 PDT 2007
On Thursday 14 June 2007 11:30, Enrique Nell wrote:
> Sí, pero lo que me interesa es obtener una estimación del tiempo
> aproximado que tardará en ejecutarse un algoritmo, independientemente
> de su eficiencia. Por ejemplo, si hago un programa que realiza algún
> tipo de operación con arrays de cadenas y lo pruebo con tamaños de
> arrays razonables
Yo habia pensado en usar un profiler que cuente las veces que se ejecutan
puntos del algoritmo y realizar una cuenta de estas operaciones.
usar esas cuentas tres grupos de datos de tamaños n 2n y 4n e intentarlos
ajustar a una curva usando logaritmos para aplanar la curva si es necesario.
Usar estos datos para predecir el tiempo usando la curva f(n) y en el caso
de superar el 80% de la memoria disponible añadir el tiempo que tardaria el
resto multipiclado por una constante C para contabilizar la swap
si m (memoria) es 10 y n 20
el tiempo seria f(20) +f(12)*C+f(4)*C.
Esto creo que te daria estimaciones que asusten a los valientes.
Més informació de la llista de correu Barcelona-pm