4551
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 17: | Строка 17: | ||
'''Диффузная модель соперника''' | '''Диффузная модель соперника''' | ||
Коэффициентом конкурентоспособности алгоритма A на базе класса <math>\Delta</math> распределения входных данных является инфимум c, такой, что алгоритм является c-конкурентным в случае, если входные данные ограничены этим классом. Это имеет место, если существует такая константа d, что для всех распределений <math>D \in \Delta</math> выполняется соотношение <math>\ | Коэффициентом конкурентоспособности алгоритма A на базе класса <math>\Delta</math> распределения входных данных является инфимум c, такой, что алгоритм является c-конкурентным в случае, если входные данные ограничены этим классом. Это имеет место, если существует такая константа d, что для всех распределений <math>D \in \Delta</math> выполняется соотношение <math>\mathbf{E}_D (A(x)) \le c \; \mathbf{E}_D (opt(x)) + d</math>, где <math>\mathbf{E}_D</math> обозначает математическое ожидание для входных данных, подчиняющихся распределению D. Коэффициентом конкурентоспособности <math>R(\Delta)</math> класса распределений <math>\Delta</math> является минимальный коэффициент конкурентоспособности, достижимый онлайновым алгоритмом на базе распределения <math>\Delta</math>. | ||
Строка 34: | Строка 34: | ||
'''Сравнительный анализ''' | '''Сравнительный анализ''' | ||
Сравнительный анализ представляет собой обобщение конкурентного анализа; он позволяет сравнивать не только отдельные алгоритмы, но и классы алгоритмов. Эта новая идея может использоваться для выявления контраста в поведении алгоритмов, | Сравнительный анализ представляет собой обобщение конкурентного анализа; он позволяет сравнивать не только отдельные алгоритмы, но и классы алгоритмов. Эта новая идея может использоваться для выявления контраста в поведении алгоритмов, подчиняющихся произвольным информационным режимам. Информационный режим представляет собой класс алгоритмов, получающих знание о входных данных одинаковым образом или с одинаковой «скоростью». Классы онлайновых и оффлайновых алгоритмов являются иллюстрациями этого понятия (первый получает входные данные шаг за шагом, второй получает всю информацию до того, как выдает какое-либо выходное значение). | ||
правка