Альтернативные показатели эффективности онлайновых алгоритмов: различия между версиями

Коэффициентом конкурентоспособности алгоритма A на базе класса <math>\Delta</math> распределения входных данных является инфимум c, такой, что алгоритм является c-конкурентным в случае, если входные данные ограничены этим классом. Это имеет место, если существует такая константа d, что для всех распределений <math>D \in \Delta</math> выполняется соотношение <math>\mathcal{E}_D (A(x)) \le c \mathcal{E}_D (opt(x)) + d</math>, где <math>\mathcal{E}_D</math> обозначает математическое ожидание для входных данных, подчиняющихся распределению D. Коэффициентом конкурентоспособности <math>R(\Delta)</math> класса распределений <math>\Delta</math> является минимальный коэффициент конкурентоспособности, достижимый онлайновым алгоритмом на базе распределения <math>\Delta</math>.

Сравнительный анализ представляет собой обобщение конкурентного анализа; он позволяет сравнивать не только отдельные алгоритмы, но и классы алгоритмов. Эта новая идея может использоваться для выявления контраста в поведении алгоритмов, следующих произвольным информационным режимам. Информационный режим представляет собой класс алгоритмов, получающих знание о входных данных одинаковым образом или с одинаковой «скоростью». Классы онлайновых и оффлайновых алгоритмов являются иллюстрациями этого понятия (первый получает входные данные шаг за шагом, второй получает всю информацию до того, как выдает какое-либо выходное значение).