Поддержание порядка в списке в за раз

Задача обслуживания заказа (или «поддержание заказа в списке») заключается в поддержке операций:

singleton: создает список с одним элементом, возвращает указатель на него
insertAfter: дает указатель на элемент, вставляет новый элемент после него, возвращает указатель на новый элемент
delete: дает указатель на элемент, удаляет его из списка
minPointer: при наличии двух указателей на элементы в одном списке возвращает тот, что ближе к началу списка

Мне известны три решения этой проблемы, которые выполняют все операции за время амортизации . Все они используют умножение. $O(1)$

Можно ли поддерживать порядок в списке за амортизированное время, не используя арифметические операции вне ? $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
источник

Умножение только недавно (начиная с Pentium III) было в . Можем ли мы включить решения, которые используют умножение?

A C^{0}

$AC^0$

Я не думаю, что это правильно. Во-первых, я не думаю, что умножение в . Во-вторых, я не думаю, что конкретные машины, такие как Pentium III, о котором вы упоминаете, имеют какое-либо отношение к вопросу о том, происходит ли умножение в . Наконец, как показано в этом вопросе, я, очевидно, знаю о нескольких алгоритмах, основанных на умножении, для этой проблемы, поэтому добавление большего числа в новый «ответ» никоим образом не улучшит ситуацию.

A C^{0}

$AC^0$

A C^{0}

$AC^0$

Jbapple

Нашел где я об этом читал; речь шла о Pentium 4, а не III; и не реализовал умножение, вместо этого обошел его с помощью новой инструкции от этого процессора: М. Торуп, «О реализациях AC0 деревьев слияния и атомных куч», в материалах четырнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, Филадельфия, Пенсильвания, США, 2003, с. 699–707.

Да!

Используйте двухуровневую структуру, как описано в конце Раздела 2 статьи Дица и Слеатора. Для верхней структуры используйте дерево козла отпущения. Используя коэффициент баланса, который может быть реализован в (например, ), мы получаем результат. $AC^0$ $2$

См. Также упражнение 8.12 из открытых структур данных и «Новый метод балансировки деревьев двоичного поиска» Роуры .

jbapple
источник

Поддержание порядка в списке в за раз

Ответы: