4551
правка
Альтернативные показатели эффективности онлайновых алгоритмов: различия между версиями
Материал из WEGA
Альтернативные показатели эффективности онлайновых алгоритмов (посмотреть исходный код)
Версия от 10:24, 26 августа 2019
, 26 августа 2019→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
В процессе конкурентного анализа эффективность онлайнового алгоритма сравнивается с эффективностью его всемогущего | В процессе конкурентного анализа эффективность онлайнового алгоритма сравнивается с эффективностью его всемогущего соперника на входных данных, относящихся к наихудшему случаю. Коэффициент конкурентоспособности алгоритма A определяется как наихудшее возможное отношение | ||
R = max | R = max | ||
A(x) opt(x) ; | A(x) opt(x) ; | ||
| Строка 15: | Строка 15: | ||
В статье Кутсупиаса и Пападимитриу предложены и исследованы два варианта уточнения подхода на базе конкурентного анализа, призванные устранить эти претензии. Первым из них является диффузная модель | В статье Кутсупиаса и Пападимитриу предложены и исследованы два варианта уточнения подхода на базе конкурентного анализа, призванные устранить эти претензии. Первым из них является диффузная модель соперника, относящаяся к случаям, в которых о входных данных кое-что известно, а именно – их вероятностное распределение. Учитывая его, оценивается эффективность алгоритма в сравнении его ожидаемой стоимости со стоимостью оптимального алгоритма для входных данных, соответствующих этому распределению. | ||
