65
правок
Изменения
page created
[[Файл:ListABCD.jpg|300px|thumb|right|Для такого списка команда <tex>\mathrm{order(D,B)}</tex> выдаст <tex>\mathrm{false}</tex>.]]
'''List order maintance''' {{---}} проблема поддержки списка со следующими командами:
* <tex>\mathrm{insert(p, q)}</tex> {{---}} вставка нового элемента <tex>p</tex> в список сразу после <tex>q</tex>;
* <tex>\mathrm{remove(p)}</tex> {{---}} удаление элемента <tex>p</tex> из списка;
* <tex>\mathrm{order(p, q)}</tex> {{---}} команда, возвращающая <tex>\mathrm{true}</tex> , если <tex>p</tex> в списке находится до <tex>q</tex> и <tex>\mathrm{false}</tex> иначе.
Существует реализация списка с командой порядка, где все операции выполняются за амортизационную <tex>O(1)</tex>.
== Алгоритм ==
Эта структура данных может быть реализована как на односвязном, так и на двусвязном списке, рассмотрим первый случай.
== См. также==
* [[Список]]
* [[Персистентный стек]]
== Источники информации ==
* [https://www.lektorium.tv/lecture/14321 {{---}} Лекция А.С. Станкевича]
* [https://en.wikipedia.org/wiki/Order-maintenance_problem {{---}} Wikipedia: order maintance problem]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]
[[Категория: Структуры данных]]
'''List order maintance''' {{---}} проблема поддержки списка со следующими командами:
* <tex>\mathrm{insert(p, q)}</tex> {{---}} вставка нового элемента <tex>p</tex> в список сразу после <tex>q</tex>;
* <tex>\mathrm{remove(p)}</tex> {{---}} удаление элемента <tex>p</tex> из списка;
* <tex>\mathrm{order(p, q)}</tex> {{---}} команда, возвращающая <tex>\mathrm{true}</tex> , если <tex>p</tex> в списке находится до <tex>q</tex> и <tex>\mathrm{false}</tex> иначе.
Существует реализация списка с командой порядка, где все операции выполняются за амортизационную <tex>O(1)</tex>.
== Алгоритм ==
Эта структура данных может быть реализована как на односвязном, так и на двусвязном списке, рассмотрим первый случай.
== См. также==
* [[Список]]
* [[Персистентный стек]]
== Источники информации ==
* [https://www.lektorium.tv/lecture/14321 {{---}} Лекция А.С. Станкевича]
* [https://en.wikipedia.org/wiki/Order-maintenance_problem {{---}} Wikipedia: order maintance problem]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]
[[Категория: Структуры данных]]
