Существует ли структура данных для ведения упорядоченного списка, которая поддерживает следующие операции за время амортизации ?
GetElement (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) должен вернуть ошибку.
Ответы:
NO.
Фредман и Сакс доказали, что любая структура данных, поддерживающая эти операции, требует не менее амортизированного времени на операцию . (Это ссылка [1] в статье Дитца, которую вы упомянули в своем первом комментарии.) Нижняя граница имеет место в очень мощной модели вычисления ячеечного зонда, которая учитывает только количество различных адресов памяти, к которым получают доступ обновление и запрос алгоритмы.Ω ( журналн / логжурналн )
Без каких-либо дополнительных предположений об операциях обновления и запросов структура данных Дитца является наилучшей (по крайней мере, с учетом постоянных факторов).
источник
Похоже, что барьер был преодолен путем модификации анализа с помощью метода хронограммы.Ω(lognloglogn)
Новая [нижняя] была доказана для аналогичных задач в модели клеточного зонда [1]. Из чтения этой статьи; Насколько я понимаю, эта граница относится и к проблеме представления списка .Ω(logn)
[1] Патраску, Михай и Эрик Д. Демейн. «Логарифмические нижние границы в модели клеточного зонда». SIAM J. Comput. 35, нет 4 (апрель 2006 г.): 932–963. DOI: 10.1137 / S0097539705447256.
источник