El problema de mantenimiento de la orden (o "mantener el orden en una lista") es apoyar las operaciones:
singleton
: crea una lista con un elemento, le devuelve un punteroinsertAfter
: dado un puntero a un elemento, inserta un nuevo elemento después de él, devolviendo un puntero al nuevo elementodelete
: dado un puntero a un elemento, lo elimina de su listaminPointer
: dado dos punteros a los elementos en la misma lista, devuelve el más cercano al principio de la lista
Soy consciente de tres soluciones a este problema que realizan todas las operaciones en tiempo amortizado. Todos usan multiplicación.
- Athanasios K. Tsakalidis: Mantener el orden en una lista vinculada generalizada
- Dietz, P., D. Sleator, dos algoritmos para mantener el orden en una lista
- Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton y Jack Zito, "Dos algoritmos simplificados para mantener el orden en una lista"
¿Se puede mantener el orden en una lista en tiempo amortizado sin utilizar ninguna operación aritmética que no esté en A C 0 ?
ds.data-structures
soft-question
pl.programming-languages
graph-theory
tree
cc.complexity-theory
pcp
co.combinatorics
cg.comp-geom
pr.probability
vc-dimension
cc.complexity-theory
complexity-classes
relativization
soft-question
advice-request
career
soft-question
research-practice
paper-review
journals
co.combinatorics
cc.complexity-theory
complexity-classes
pr.probability
average-case-complexity
cc.complexity-theory
lo.logic
descriptive-complexity
finite-model-theory
ds.algorithms
cc.complexity-theory
approximation-hardness
csp
pcp
cc.complexity-theory
circuit-complexity
jbapple
fuente
fuente
Respuestas:
¡Si!
Consulte también el ejercicio 8.12 de las estructuras de datos abiertos y el "Un nuevo método para equilibrar los árboles de búsqueda binarios" de Roura .
fuente