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

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

Особый интерес представляют алгоритмы обновления списков, работающие в режиме ''онлайн'', т. е. каждый запрос обрабатывается без знания о будущих запросах. Производительность онлайн-алгоритмов обычно оценивается при помощи ''сравнительного анализа''. Здесь онлайновая стратегия сравнивается с оптимальным оффлайновым алгоритмом, который заранее знает всю последовательность запросов и может обработать ее с минимальными затратами. Пусть имеется последовательность запросов <math>\sigma</math>. Обозначим за <math>A(\sigma)</math> затраты, понесенные онлайн-алгоритмом <math>A</math> при обработке последовательности <math>\sigma</math>, а за <math>OPT(\sigma)</math> – затраты, понесенные оптимальным офлайн-алгоритмом OPT. Онлайн-алгоритм <math>A</math> называется <math>c</math>-конкурентным, если существует константа <math>\alpha</math> такая, что для списков любых размеров и всех последовательностей запросов <math>\sigma</math> выполняется соотношение <math>A(\sigma) \le c \cdot OPT(\sigma) + \alpha</math>. Коэффициент <math>c</math> также называется ''коэффициентом конкурентоспособности''. Конкурентоспособность должна быть одинаковой для ''списков любых размеров''.