Algoritmo de puntero

En informática , un algoritmo de punteros (a veces llamado máquina de punteros o máquina de referencias; véase el artículo « Máquina de punteros» para un concepto similar, aunque no idéntico) es un tipo de algoritmo que gestiona una estructura de datos enlazada. Este concepto se utiliza como modelo para pruebas de límites inferiores, y las restricciones específicas sobre la estructura de datos enlazada y el acceso del algoritmo a la misma varían.

Este modelo se ha utilizado ampliamente con problemas relacionados con la estructura de datos de conjuntos disjuntos . Así, Tarjan y La Poutré utilizaron este modelo para demostrar cotas inferiores en la complejidad amortizada de una estructura de datos de conjuntos disjuntos ^{[ 1 ] [ 2 ]} (La Poutré también abordó el problema de división y búsqueda de intervalos ). Blum utilizó este modelo para demostrar una cota inferior en el tiempo de peor caso de una sola operación de la estructura de datos de conjuntos disjuntos. ^{[ 3 ]} Blum y Rochow demostraron una cota inferior en el peor caso para el problema de unión y búsqueda de intervalos . ^{[ 4 ]}

En la cota inferior de Tarjan para el problema de la unión de conjuntos disjuntos, las suposiciones sobre el algoritmo son:

• El algoritmo mantiene una estructura de nodos enlazados.
• Cada elemento del problema está asociado a un nodo.
• Cada conjunto está representado por un nodo.
• Los nodos de cada conjunto constituyen un componente conectado distinto en la estructura (esta propiedad se denomina separabilidad ).
• La operación de búsqueda se realiza siguiendo los enlaces desde el nodo del elemento hasta el nodo del conjunto.

Bajo estos supuestos, el límite inferior de${\displaystyle \Omega (m\alpha (m,n))}$Se demuestra que el costo de una secuencia de m operaciones es menor.