Онлайн-алгоритм обновления списков: различия между версиями

Обновление списков представляет собой классическую онлайновую задачу и, наряду с задачей о подкачке страниц, является первой проблемой, которая была изучена с точки зрения конкурентоспособности. Задача обновления списков заключается в поддержании словаря в виде несортированного линейного списка. Рассмотрим множество элементов, представленное в виде линейного цепного списка. Системе предъявляется последовательность запросов <math>\sigma</math>, где каждый запрос представляет собой одну из следующих операций. Это может быть (1) ''доступ'' к элементу списка, (2) ''вставка'' нового элемента в список или (3) ''удаление'' элемента. Чтобы выполнить доступ к элементу, алгоритм обновления списков начинает с первых элементов списка и линейно перебирает элементы, пока не будет найден нужный. Для вставки нового элемента алгоритм сначала сканирует весь список, чтобы убедиться, что этого элемента еще нет, а затем вставляет его в конец списка. Для удаления элемента алгоритм сканирует список в поисках элемента, а затем удаляет его.

При обработке запросов алгоритм обновления списков несет накладные расходы. Если запрос является операцией доступа или удаления, то накладные расходы равны <math>i</math>, где <math>i</math> – позиция запрашиваемого элемента в списке. Если запрос является вставкой, то затраты равны <math>n + 1</math>, где <math>n</math> – количество элементов в списке перед вставкой. В процессе обработки последовательности запросов алгоритм обновления списков может перестроить список. Сразу после доступа или вставки запрошенный элемент может быть перемещен без дополнительных расходов на любую позицию, расположенную ближе к началу списка. Такие обмены называются ''бесплатными''. При помощи бесплатных обменов алгоритм может снизить стоимость последующих запросов. В любой момент времени два соседних элемента в списке могут быть обменены с затратами 1. Такие обмены называются ''платными''. Цель состоит в том, чтобы обработать последовательность запросов так, чтобы суммарная стоимость была как можно ниже.