Manter a ordem numa lista em

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 ? $O(1)$ $AC^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
fonte

A multiplicação apenas recentemente (desde Pentium III) esteve em

. Podemos incluir soluções que usam multiplicação?

A C^{0}

$AC^0$

A C^{0}

$AC^0$

A C^{0}

$AC^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.

Respostas: