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

Abstract

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.