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

Antonio Sedeño Noda , Carlos González Martín , Sergio Alonso Rodríguez

• español

  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.

• English

  The complexity of an algorithm is the measurement of the efficiency with which the solution of a problem is found. A valid measurement can be successfully used to make comparisons between severa! algorithms and as a estimator of the time of resolution. Then, it is had to be independent of the machine selected to solve the problem, and the subjective aspects of the programmer. Worst case complexity fulfills these two properties, but nevertheless, it is based on the establishment of certain bounds only valid by rare problems. The concept of virtual CPU time is introduced by Ahuja, Magnanti and Orlin, to provide the two properties mentioned to the computational experiments through the specification of the denominated representative operations of the algorithm. In this work this complexity study is applied to the two-phases double capacities-scaling algorithm developed by Sedeño Noda and González Martín.