Manter a ordem numa lista em

15

O problema de manutenção de pedidos (ou "manutenção de pedidos em uma lista") é dar suporte às operações:

  • singleton: cria uma lista com um item, retorna um ponteiro para ele
  • insertAfter: dado um ponteiro para um item, insere um novo item depois dele, retornando um ponteiro para o novo item
  • delete: dado um ponteiro para um item, remove-o da sua lista
  • minPointer: dado dois ponteiros para itens da mesma lista, retorna o mais próximo da frente da lista

Estou ciente de três soluções para esse problema que executam todas as operações em tempo amortizado. Todos eles usam multiplicação.O(1)

O pedido pode ser mantido em uma lista em tempo amortizado sem o uso de operações aritméticas que não estejam em A C 0 ?O(1)UMAC0 0

jbapple
fonte
A multiplicação apenas recentemente (desde Pentium III) esteve em . Podemos incluir soluções que usam multiplicação? UMAC0 0
AT
UMAC0 0UMAC0 0
Encontrei onde li sobre isso; tratava-se de Pentium 4 e não III; e não implementou a multiplicação. PA, EUA, 2003, pp. 699–707.
AT

Respostas: