4817
правок
Обмен пакетами при переключении между несколькими очередями: различия между версиями
Материал из WEGA
Обмен пакетами при переключении между несколькими очередями (посмотреть исходный код)
Версия от 07:01, 8 января 2020
, 8 января 2020→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 27: | Строка 27: | ||
'''Детерминированные алгоритмы''' | '''Детерминированные алгоритмы''' | ||
Теорема 1 [1]. Для любого размера буфера B коэффициент конкурентоспособности каждого детерминированного онлайнового алгоритма не может быть меньше ( | '''Теорема 1 [1]. Для любого размера буфера B коэффициент конкурентоспособности каждого детерминированного онлайнового алгоритма не может быть меньше <math>(e_B + \frac{2}{B}) / (e_B - 1 + \frac{1}{B}) \ge \frac{e}{e - 1} \approx 1,58</math>, где <math>e_B = ((B + 1)/B)^B</math>.''' | ||
Теорема 2 | '''Теорема 2 [4]. Каждый сохраняющий работу онлайновый алгоритм является 2-конкурентным.''' | ||
Теорема 3 [ | '''Теорема 3 [1]. Для любого размера буфера B коэффициент конкурентоспособности любого жадного алгоритма, который всегда обслуживает самую длинную очередь (LQF), не может быть меньше <math>2 - \frac{1}{B}</math>, если <math>m \gg B</math>.''' | ||
