Mantener el orden en una lista en

15

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 puntero
  • insertAfter: dado un puntero a un elemento, inserta un nuevo elemento después de él, devolviendo un puntero al nuevo elemento
  • delete: dado un puntero a un elemento, lo elimina de su lista
  • minPointer: 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.O(1)

¿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 ?O(1)UNC0 0

jbapple
fuente
La multiplicación solo recientemente (desde Pentium III) ha estado en . ¿Podemos incluir soluciones que usen la multiplicación? UNC0 0
AL
UNC0 0UNC0 0
Encontrado donde leí sobre esto; se trataba de Pentium 4 no III; y no implementó la multiplicación, en cambio funcionó con una nueva instrucción de ese procesador: M. Thorup, 'On AC0 Implementations of Fusion Trees and Atomic Heaps', en Proceedings of the Decimocuarto Simposio Anual ACM-SIAM sobre Algoritmos Discretos, Filadelfia, PA, EE. UU., 2003, págs. 699–707.
AL

Respuestas: