Конкурентный анализ — это метод, изобретенный для анализа онлайн-алгоритмов , в котором производительность онлайн-алгоритма (который должен удовлетворять непредсказуемую последовательность запросов, выполняя каждый запрос, не имея возможности видеть будущее) сравнивается с производительностью оптимального автономного алгоритма. который может заранее просмотреть последовательность запросов. Алгоритм является конкурентоспособным , если его коэффициент конкурентоспособности (отношение между его производительностью и производительностью автономного алгоритма) ограничен. В отличие от традиционного анализа наихудшего случая , когда производительность алгоритма измеряется только для «жестких» входных данных, конкурентный анализ требует, чтобы алгоритм работал хорошо как на жестких, так и на простых входных данных, где «сложные» и «простые» определяются производительностью. оптимального автономного алгоритма.
Для многих алгоритмов производительность зависит не только от размера входных данных, но и от их значений. Например, сортировка массива элементов различается по сложности в зависимости от начального порядка. Такие зависящие от данных алгоритмы анализируются для данных среднего и худшего случая. Конкурентный анализ — это способ анализа наихудшего случая для онлайновых и рандомизированных алгоритмов , которые обычно зависят от данных.
В конкурентном анализе представляют себе «противника», который намеренно выбирает сложные данные, чтобы максимизировать соотношение стоимости изучаемого алгоритма и некоторого оптимального алгоритма. При рассмотрении рандомизированного алгоритма необходимо также различать забывчивого противника , который не знает о случайном выборе, сделанном противостоящим ему алгоритмом, и адаптивного противника , который полностью знает внутреннее состояние алгоритма в любой момент его выполнения. . (Для детерминированного алгоритма нет никакой разницы; любой противник может просто вычислить, какое состояние этот алгоритм должен иметь в любой момент в будущем, и соответственно выбрать сложные данные.)
Например, алгоритм быстрой сортировки выбирает один элемент, называемый «центр», то есть в среднем не слишком далеко от центрального значения сортируемых данных. Затем быстрая сортировка разделяет данные на две стопки, одна из которых содержит все элементы со значением меньше значения опорной точки, а другая — остальные элементы. Если быстрая сортировка выбирает опорную точку каким-то детерминированным образом (например, всегда выбирая первый элемент в списке), то злоумышленнику легко заранее упорядочить данные, чтобы быстрая сортировка выполнялась в наихудшее время. Однако если быстрая сортировка выбирает какой-то случайный элемент в качестве опорного, то злоумышленник, не зная, какие случайные числа появляются, не сможет упорядочить данные так, чтобы гарантировать время выполнения быстрой сортировки в наихудшем случае.
Классической онлайн-проблемой, впервые анализируемой с помощью конкурентного анализа (Sleator & Tarjan 1985), является проблема обновления списка : учитывая список элементов и последовательность запросов на различные элементы, минимизируйте стоимость доступа к списку, в котором элементы ближе к доступ к началу списка обходится дешевле. (Обычно стоимость доступа к элементу равна его положению в списке.) После доступа список можно переупорядочить. Большинство перестановок имеют свою цену. Алгоритм Move-To-Front просто перемещает запрошенный элемент на передний план после доступа без каких-либо затрат. Алгоритм транспонирования заменяет доступный элемент на элемент, расположенный непосредственно перед ним, также бесплатно. Классические методы анализа показали, что транспонирование оптимально в определенных контекстах. На практике Move-To-Front показал себя намного лучше. Конкурентный анализ был использован, чтобы показать, что противник может заставить Transpose работать сколь угодно плохо по сравнению с оптимальным алгоритмом, тогда как Move-To-Front никогда не может потребовать более чем двукратной стоимости оптимального алгоритма.
В случае онлайн-запросов с сервера используются конкурентные алгоритмы для преодоления неопределенности относительно будущего. То есть алгоритм не «знает» будущее, а воображаемый противник («конкурент») «знает». Аналогично, конкурентные алгоритмы были разработаны для распределенных систем, где алгоритм должен реагировать на запрос, поступающий в одно место, не «зная», что только что произошло в удаленном месте. Эта установка была представлена в (Awerbuch, Kutten & Peleg 1992).