Estimación del tiempo virtual de CPU del algoritmo de dos fases doblemente escalado en las capacidades

Resumen

La complejidad de un algoritmo es la medida de eficiencia con la que éste halla la solución a un problema. Para que sea una medida válida que pueda ser usada para realizar con éxito comparaciones entre varios algoritmos y como estimador del tiempo de resolución, se ha de independizar de la máquina usada para el experimento computacional y de aspectos subjetivos dependientes del programador. La complejidad en el caso peor cumple con estas dos propiedades, y sin embargo, se basa en el establecimiento de cotas superiores para el tiempo de CPU sólo alcanzables por los problemas de condiciones más desfavorables. Por ello, se introduce entonces el concepto de tiempo virtual de CPU, que dota a los experimentos computacionales de las dos propiedades mencionadas a través de la localizaci.ón de las denominadas operaciones representativas del algoritmo estudiado. En este trabajo se aplica este tipo de estudio, introducido por Ahuja, Magnanti y Orlin al algoritmo de dos fases doblemente escalado en las capacidades desarrollado por Sedeño Noda y González Martín.