Resumen de Reducción del tiempo de acceso en memorias tipo disco, mediante ordenación de los registros. Algoritmos de aproximación

José María Troya Linero , Antonio Vaquero Sánchez

• El tiempo medio de acceso a una memoria secundaria puede reducirse ordenando los registros en función de las posibilidades de acceso. Cuando existen relaciones entre los registros, el problema de encontrar la ordenación óptima es NP-duro. Por tanto, no puede obtenerse la solución óptima en tiempo polinomial. Como el número de registros o bloques de registros almacenados en una memoria secundaria tipo disco es muy elevado, es necesario buscar algoritmos que encuentren soluciones aproximadas.

  En este artículo damos tres algoritmos de aproximación de diferente complejidad y estudiamos su rendimiento.