[bcn-pm] Complejidad de algoritmos

[José Luis Pérez Diez]

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.