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

  1. Troya Linero, José María
  2. Vaquero Sánchez, Antonio
Revista:
Revista de informática y automática

ISSN: 0210-8712

Año de publicación: 1982

Año: 15

Número: 54

Páginas: 5-12

Tipo: Artículo

Otras publicaciones en: Revista de informática y automática

Resumen

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.