[bcn-pm] Complejidad de algoritmos

Enrique Nell blas.gordonagmail.com
Dme Jun 13 06:48:33 PDT 2007


Hola

Al leer las diapositivas de una de las charlas de la YAPC::NA::2007,
http://www.mawode.com/~waltman/talks/approx_ppw.pdf, me he acordado de
algo a lo que empecé a dar vueltas recientemente, aunque no me siento
preparado para abordar el problema.
¿Conocéis alguna manera de realizar una estimación del tiempo que
tardará en ejecutarse un algoritmo basada en la memoria requerida por
las estructuras de datos de partida, la memoria RAM disponible y la
velocidad del procesador? Sería algo así como hacer un benchmark
aproximado a priori que permita, por ejemplo, dar al usuario de un
programa la posibilidad de elegir ejecutar o no una función según el
tiempo de ejecución estimado para los datos en cuestión.
Como no tengo apenas conocimientos sobre complejidad algorítmica, lo
primero que se me ocurrió fue usar un enfoque empírico: medir tiempos
de referencia para estructuras de datos de distintos tamaños en una
máquina y utilizar ese test kit para medir los valores
correspondientes durante la configuración del programa en otra
máquina, a fin de extrapolar los tiempos para una máquina con memoria
y velocidad de procesador distintas, pero sospecho que no debe de ser
tan sencillo y, entre otras cosas, dependerá de la complejidad de los
algoritmos (vamos, que creo que no me libraré de medirla).
Agradeceré todas las pistas y referencias de lectura que podáis darme.

Saludos
Enrique


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