[bcn-pm] Complejidad de algoritmos

Enrique Nell blas.gordonagmail.com
Dij Jun 14 06:48:01 PDT 2007


Gracias, probaré algo así.

Enrique


> Hola Enrique,
>
> Puedes, establecer un modelo matematico para la complejidad de tu
> algoritmo y con algunos benchmarks ajustarlo.
>
> Por ejemplo, si tienes un script que ordena algo, tipicamente su
> complejidad sera O(NlogN), osea, que el tiempo que tardara en ejecutarse
> es una funcion
>
>    t(n) = A + B * n + C * n log n
>
> Si mides los tiempos de ejecucion del script para distintos valores de
> n, tendras un conjunto de pares (n1, t1), (n2, t2)...(nm, tm) con los
> cuales podras ajustar los valores de A, B y C minimizando el error.
>
> Luego, podras calcular el tiempo de ejecucion estimado de tu script, sin
> mas que calcular t(n) para el n que quieras.
>
> De todas formas, al final se trata de una extrapolacion, y como el
> modelo matematico utilizado es muy simple los resultados solo seran
> validos en un entorno limitado. Osea, que si haces benchmarks para n =
> 1, 2, 4, 8, 16, 32, 64 y 128, probablemente, el resultado que obtengas
> para n = 256, 512 o 1024 no se aleje mucho de la realidad, pero para n =
> 1_000_000 es probable que no tenga nada que ver.
>
> Tambien tienes que considerar que como comentaban en otro correo, los
> tama~nos de memoria de cache, RAM y swap tambien afectan a la velocidad
> de un algoritmo. La misma aproximacion que comentaba antes puede ser
> utilizada para estimar el consumo de memoria.
>
> - Salva


Més informació de la llista de correu Barcelona-pm