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

В процессе конкурентного анализа эффективность онлайнового алгоритма сравнивается с эффективностью его всемогущего соперника на входных данных, относящихся к наихудшему случаю. Коэффициент конкурентоспособности алгоритма A определяется как наихудшее возможное отношение <math>R_A = max_x \frac{A(x)}{opt(x)}</math>, где x пробегает все возможные входные данные задачи, а A(x) и opt(x) представляют собой стоимость решений, полученных алгоритмом A, и оптимальный оффлайновый алгоритм для входного значения x, соответственно [''Все задачи в данной статье предполагаются онлайновыми задачами минимизации, следовательно, цель заключается в минимизации затрат. Все представленные здесь результаты действительны и для онлайновых задач максимизации с соответствующими корректировками в определениях'']. Это понятие может быть расширено для определения коэффициента конкурентности задачи как минимального коэффициента конкурентности алгоритма ее решения, а именно <math>R = min_A R_A = min_A max_x \frac{A(x)}{opt(x)}.</math>

Основная критика данного подхода заключалась в том, что из-за характерного пессимизма, присущего всем типам анализа наихудших вариантов, ему не удается различать алгоритмы, демонстрирующие разную эффективность при разных условиях. Кроме того, алгоритмам, которые «пытаются» работать лучше по сравнению со своими метриками для наихудшего случая, часто не удается показать эффективное поведение для различных «типичных» входных данных. Эти аргументы проще проверить в тех (редких) сценариях, где выполняется очень сильное предположение, заключающееся в том, что о распределении входных данных ''ничего'' не известно. Однако на практике такое редко встречается.

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