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

Коэффициентом конкурентоспособности алгоритма 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>.