Структура данных с поиском, вставкой и удалением за амортизированное время ?

25

Существует ли структура данных для ведения упорядоченного списка, которая поддерживает следующие операции за время амортизации ?O(1)

  • GetElement (k) : возвращает й элемент списка.k

  • InsertAfter (x, y) : вставить новый элемент y в список сразу после x.

  • Удалить (x) : удалить x из списка.

Для последних двух операций вы можете предположить, что x указан как указатель непосредственно на структуру данных; InsertElement возвращает соответствующий указатель для y. InsertAfter (NULL, y) вставляет y в начало списка.

Например, начиная с пустой структуры данных, следующие операции обновляют упорядоченный список, как показано ниже:

  • InsertAfter (NULL, a) [a]
  • InsertAfter (NULL, b) [b, a]
  • InsertAfter (b, c) [b, c, a]
  • InsertAfter (a, d) [b, c, a, d]
  • Удалить (c) [b, a, d]

После этих пяти обновлений GetElement (2) должен вернуть d, а GetElement (3) должен вернуть ошибку.

В
источник
2
В « Оптимальных алгоритмах индексации списка и ранга подмножества» (1989 г.) я нашел решение этой проблемы. Ω(log nlog log n)
AT
2
@ Рафаэль: Я думаю, он имеет в виду элемент, который будет называться если структура данных будет массивом. Массивы поддерживают первую операцию за время но не вторую; связанные списки поддерживают вторую операцию за время но не первую. O ( 1 ) O ( 1 )A[k]O(1)O(1)
Джефф
2
Также сбалансированные двоичные деревья поддерживают обе операции за времени. O(logn)
Джефф
1
@ Рафаэль: отредактировано, чтобы уточнить.
Джефф
2
@JeffE динамический массив поддерживает первые два за амортизированное время ( cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf )O(1)
Диего

Ответы:

33

NO.

Фредман и Сакс доказали, что любая структура данных, поддерживающая эти операции, требует не менее амортизированного времени на операцию . (Это ссылка [1] в статье Дитца, которую вы упомянули в своем первом комментарии.) Нижняя граница имеет место в очень мощной модели вычисления ячеечного зонда, которая учитывает только количество различных адресов памяти, к которым получают доступ обновление и запрос алгоритмы.Ω(logn/loglogn)

Без каких-либо дополнительных предположений об операциях обновления и запросов структура данных Дитца является наилучшей (по крайней мере, с учетом постоянных факторов).

JeffE
источник
3
@AT: эта оценка никогда не была «доказана неправильно». Есть ситуации, когда это не применимо, но это совершенно другое утверждение!
Рафаэль
5
@AT: нижняя граница сортировки была доказана в гораздо более слабой модели вычислений, а именно в бинарных деревьях решений. Оценка была «доказана неправильно» путем разработки более быстрых алгоритмов, которые нельзя описать как бинарные деревья решений. Чтобы доказать неверную оценку Фредмана и Сакса, вам нужно будет разработать более быстрый алгоритм, который не обращается к памяти . Удачи.
Джефф
@JeffE и Рафаэль; пожалуйста, просмотрите мой другой ответ и подтвердите / опровергните мой результат, когда вы получите шанс. Спасибо.
AT
6

Похоже, что барьер был преодолен путем модификации анализа с помощью метода хронограммы.Ω(lognloglogn)

Новая [нижняя] была доказана для аналогичных задач в модели клеточного зонда [1]. Из чтения этой статьи; Насколько я понимаю, эта граница относится и к проблеме представления списка .Ω(logn)


[1] Патраску, Михай и Эрик Д. Демейн. «Логарифмические нижние границы в модели клеточного зонда». SIAM J. Comput. 35, нет 4 (апрель 2006 г.): 932–963. DOI: 10.1137 / S0097539705447256.

В
источник
1
Эта нижняя граница верна для слов постоянного размера, тогда как ранняя нижняя граница предназначена для слов логарифмического размера. Ω(logn/loglogn)
Юваль Фильмус
Верно. Кроме того, можете ли вы подтвердить, что эта граница относится к проблеме представления списка со словами постоянного размера?
AT
1
Я могу подтвердить это из-за того, что Вы упомянули Дитца ( hdl.handle.net/1802/5694 ). Это делает сложность точно , и поэтому не . Ω ( log n )Θ(logn/loglogn) Ω(logn)
Jbapple