Конкурентний аналіз (онлайн алгоритм)

Змаговий аналіз — це метод для аналізу онлайн алгоритмів, в якому швидкодія онлайн алгоритму (який працює з непередбачною послідовністю запитів, опрацьовуючи кожен запит не бачачи майбутнього) порівнюється зі швидкодією оптимального офлайн алгоритму, який може бачити послідовність запитів заздалегідь. Кажуть, що алгоритм змаговий, якщо його співвідношення змаговості — співвідношення між його швидкодією і швидкодією офлайн алгоритму — обмежене. На відміну від традиційного ^[en], де швидкодія алгоритму виміряється лише для «складних» входів, змаговий аналіз вимагає, щоб алгоритм однаково добре поводився як на легких так і на складних входах, де «легкість» і «складність» визначені швидкодією оптимального офлайн алгоритму.

Для багатьох алгоритмів, швидкодія залежить не тільки від розміру входів, але й від їхніх значень. Наприклад, складність сортування масиву різниться залежно від початкового порядку елементів. Такі залежні від даних алгоритми аналізують для середнього випадку і для найгіршого випадку. Змаговий аналіз це спосіб виконання аналізу найгіршого випадку для онлайн і увипадковлених алгоритмів, які зазвичай залежні від даних.

У змаговому аналізі, ми уявляємо «суперника», який навмисно обирає складні дані, щоб унайбільшити співвідношення ціни між алгоритмом, що ми його розглядаємо, і деяким оптимальним алгоритмом. Розглядаючи увипадковлений алгоритм, ми мусимо далі розрізняти між неуважним суперником, який не знає про випадкові вибори, які робить алгоритм проти якого він змагається, і пристосовним суперником, який має повне знання про внутрішній стан алгоритму в будь-яку мить під час виконання. (Для детермінованого алгоритму різниці немає; будь-який з противників може просто обчислити, який стан повинен мати цей алгоритм у будь-який час у майбутньому і відповідно вибрати складні дані.)