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

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

Эта модель применяется к традиционной задаче подкачки для класса распределений <math>\Delta_{\epsilon}</math>. Этот класс содержит все распределения вероятностей, такие, что для заданной последовательности запросов и страницы p вероятность того, что p является следующей запрошенной страницей, не выше e. Было показано, что хорошо известный онлайновый алгоритм LRU достигает оптимального коэффициента конкурентоспособности R(A€) для всех e, иначе говоря, что он является оптимальным по отношению к любому сопернику, использующему распределение этого класса.