Una lista autoorganizada es una lista que reordena sus elementos basándose en alguna heurística de autoorganización para mejorar el tiempo de acceso promedio . El objetivo de una lista autoorganizada es mejorar la eficiencia de la búsqueda lineal moviendo los elementos a los que se accede con mayor frecuencia hacia el principio de la lista. Una lista autoorganizada logra un tiempo casi constante para el acceso a los elementos en el mejor de los casos. Una lista autoorganizada utiliza un algoritmo de reorganización para adaptarse a varias distribuciones de consultas en tiempo de ejecución.
El concepto de listas autoorganizadas tiene sus raíces en la idea de la organización de actividades de registros en archivos almacenados en discos o cintas. [1] Una discusión frecuentemente citada de archivos y listas autoorganizadas es la de Knuth. [2] John McCabe realizó los primeros análisis de complejidad algorítmica de la estrategia Mover al frente (MTF) donde un elemento se mueve al frente de la lista después de que se accede a él. [3] Analizó el tiempo promedio necesario para que una lista ordenada aleatoriamente alcance el orden óptimo. El orden óptimo de una lista es aquel en el que los elementos se ordenan en la lista según la probabilidad con la que serán necesarios, con el elemento más accedido primero. El orden óptimo puede no conocerse de antemano y también puede cambiar con el tiempo.
McCabe introdujo la estrategia de transposición, en la que un elemento al que se accede se intercambia con el elemento que se encuentra delante de él en la lista. Conjeturó que, en el caso promedio, la transposición funcionaba al menos tan bien como la MTF para acercarse al ordenamiento óptimo de los registros en el límite. Esta conjetura fue demostrada posteriormente por Rivest. [4] McCabe también observó que, tanto con la heurística de transposición como con la MTF, se alcanzaría el ordenamiento óptimo de los registros incluso si la heurística solo se aplicara cada N acceso, y que se podría elegir un valor de N que reflejara el coste relativo de reubicar los registros con el valor de acercarse al ordenamiento óptimo más rápidamente. Se realizaron más mejoras y se sugirieron algoritmos por parte de investigadores como: Rivest, Tenenbaum y Nemes, Knuth y Bentley y McGeoch (por ejemplo, análisis del peor de los casos para heurísticas de búsqueda secuencial autoorganizadas).
Una lista autoorganizada utiliza una heurística autoorganizada, un algoritmo que modifica una estructura de datos , como una lista enlazada, en respuesta al uso de la estructura de datos.
Algunos ejemplos de heurísticas autoorganizativas incluyen: