Reducción del tiempo de acceso en memorias tipo disco, mediante ordenación de los registros. Algoritmos de aproximación
- Troya Linero, José María
- Vaquero Sánchez, Antonio
ISSN: 0210-8712
Datum der Publikation: 1982
Jahr: 15
Nummer: 54
Seiten: 5-12
Art: Artikel
Andere Publikationen in: Revista de informática y automática
Zusammenfassung
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.