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

В формулировках алгоритмов обновления списка обычно предполагается, что последовательность запросов состоит только из доступов. Достаточно очевидно, как можно расширить алгоритмы, чтобы они также могли обрабатывать вставки и удаления. При вставке алгоритм сначала добавляет новый элемент в конец списка, а затем выполняет те же действия, как если бы элемент был запрошен впервые. При удалении алгоритм сначала ищет элемент, а затем просто удаляет его.

Сначала рассмотрим алгоритмы Move-To-Front, Transpose и Frequency-Count. Отметим, что Move-To-Front и Transpose – стратегии ''без памяти'', то есть им не требуется дополнительная память для принятия решения о том, куда переместить запрошенный элемент. Таким образом, с практической точки зрения они более привлекательны, чем Frequency-Count. Слейтор и Тарьян [16] проанализировали коэффициенты конкурентоспособности этих трех алгоритмов.

'''Алгоритм «Комбинация» (Combination)''': с вероятностью <math>\frac{4}{5}</math> алгоритм обрабатывает последовательность запросов, используя Bit, и с вероятностью <math>\frac{1}{5}</math> обрабатывает последовательность запросов, используя Timestamp.

Амбюл и др. [4] представили нижнюю границу для рандомизированных алгоритмов обновления списков.

'''Теорема 5 [4]. Пусть A – рандомизированный онлайн-алгоритм для задачи обновления списков. Если A <math>c</math>-конкурентен относительно любого рассеянного соперника, то с > 1,50084.'''

До сих пор в данной статье рассматривались онлайновые алгоритмы. В оффлайновом варианте задачи обновления списков вся последовательность запросов <math>\sigma</math> известна заранее. Амбюл [3] показал, что оффлайновый вариант является NP-трудным.

Что касается истории задачи об обновлении списков, то до появления сравнительного анализа алгоритмы обновления списков изучались в сценариях, где последовательности запросов формируются в соответствии с вероятностными распределениями. Асимптотические ожидаемые затраты, понесенные онлайновым алгоритмом при обработке одного запроса, сравнивались с соответствующими затратами, понесенными при оптимальном статическом упорядочивании. Существует большой объем литературы по этой теме. Чанг и др. [11] показали, что для любого распределения асимптотическая стоимость обработки алгоритма Move-To-Front не более чем в <math>\frac{\pi}{2}</math> раз превышает стоимость обработки оптимального упорядочения.