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