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

В процессе конкурентного анализа эффективность онлайнового алгоритма сравнивается с эффективностью его всемогущего противника на входных данных, относящихся к наихудшему случаю. Коэффициент конкурентоспособности алгоритма A определяется как наихудшее возможное отношение

В статье Кутсупиаса и Пападимитриу предложены и исследованы два варианта уточнения подхода на базе конкурентного анализа, призванные устранить эти претензии. Первым из них является диффузная модель противника, относящаяся к случаям, в которых о входных данных кое-что известно, а именно – их вероятностное распределение. Учитывая его, оценивается эффективность алгоритма в сравнении его ожидаемой стоимости со стоимостью оптимального алгоритма для входных данных, соответствующих этому распределению.