4846
правок
Подкачка страниц: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 12: | Строка 12: | ||
== Основные результаты == | == Основные результаты == | ||
Основным вкладом работы Слейтора и Тарьяна [6] стала идея конкурентного анализа. В этом типе анализа производительность онлайнового алгоритма сравнивается с производительностью оптимального оффлайнового алгоритма OPT. Оффлайновый алгоритм знает все входные данные и, более того, может использовать неограниченные вычислительные ресурсы для поиска наилучшего возможного решения для этих входных данных. | Основным вкладом работы Слейтора и Тарьяна [6] стала идея ''конкурентного анализа''. В этом типе анализа производительность онлайнового алгоритма сравнивается с производительностью оптимального оффлайнового алгоритма OPT. Оффлайновый алгоритм знает все входные данные и, более того, может использовать неограниченные вычислительные ресурсы для поиска наилучшего возможного решения для этих входных данных. | ||
Обозначим стоимость алгоритма ALG на входной последовательности | Обозначим стоимость алгоритма <math>ALG</math> на входной последовательности <math>\sigma</math> за <math>ALG(\sigma)</math>. Онлайновый алгоритм <math>\mathcal{A}</math> называется c-конкурентным, если существует константа <math>b</math>, такая, что для каждой последовательности запросов <math>\sigma</math> выполняется соотношение | ||
(1) A( | (1) <math>\mathcal{A}(\sigma) \le с \cdot ОРТ(\sigma) + b</math>. | ||
Коэффициентом конкурентоспособности алгоритма A является наименьшее значение c, такое, что A остается c-конкурентным. Это определение очень похоже на определение коэффициента аппроксимации для алгоритмов аппроксимации. Однако следует отметить, что на онлайновый алгоритм не накладывается никаких вычислительных ограничений. В частности, ему разрешается использовать экспоненциальное время для принятия решений. Таким образом, коэффициент конкурентоспособности измеряет исключительно потерю производительности, возникающую из-за незнания будущего. | Коэффициентом конкурентоспособности алгоритма <math>\mathcal{A}</math> является наименьшее значение <math>c</math>, такое, что <math>\mathcal{A}</math> остается c-конкурентным. Это определение очень похоже на определение коэффициента аппроксимации для алгоритмов аппроксимации. Однако следует отметить, что на онлайновый алгоритм не накладывается никаких вычислительных ограничений. В частности, ему разрешается использовать экспоненциальное время для принятия решений. Таким образом, коэффициент конкурентоспособности измеряет исключительно потерю производительности, возникающую из-за незнания будущего. | ||