16
правок
Изменения
Нет описания правки
Любой <tex>\alpha</tex>-оптимальный онлайн детерминированный алгоритм кэширования имеет <tex>\alpha \geqslant k</tex>.
|proof =
Обозначим <tex>T_\text{opt}(\sigma)</tex> и <tex>T_\text{det}(\sigma)</tex> как время работы оптимального и детерминированного алгоритма на входе <tex>\sigma</tex>. По определению <tex>\alpha</tex>-оптимальности имеем <tex>\forall\sigma \quad ; T_\text{det}(\sigma) < \alpha \cdot T_\text{opt}(\sigma) + C</tex>. Покажем, что достаточно построить для любого <tex>n</tex> такую последовательность запросов <tex>\sigma_n</tex>, что <tex>T_\text{det}(\sigma_n) \geqslant k \cdot T_\text{opt}(\sigma_n) + C_0</tex>. Так как <tex>\lim\limits_{n->\infty}T = \infty</tex>, получаем <tex>\lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \geqslant k</tex>. С другой стороны можно квантор раскрыть для значения <tex>\sigma_n</tex>: <tex>T_\text{det}(\sigma_n) < \alpha \cdot T_\text{opt}(\sigma_n) + C</tex>, а потом снова перейти к пределу <tex>\lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \leqslant \alpha</tex>. Перепишем неравенства в следующем виде <tex>k \leqslant \lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \leqslant \alpha</tex>, откуда очевидно, что <tex>\alpha \geqslant k</tex>.
Теперь построим <tex>\sigma_n</tex>. В последовательности будем использовать только <tex>k + 1</tex> различных запросов. Первыми <tex>k</tex> запросами возьмём любые различные, а дальше, каждым следующим запросом поставим тот, результата которого нет в данный момент в кэше детерминированного алгоритма. Это хоть и не явное, но корректное задание последовательности, потому что имея алгоритм, мы можем вычислить каждый запрос в <tex>\sigma_n</tex> на основе предыдущих. Очевидно, что <tex>T_\text{det}(\sigma_n) = n</tex>.
Посмотрим как на <tex>\sigma_n</tex> будет работать следующий, возможно оптимальный оффлайн алгоритм (индекс mopt). Первые k элементов алгоритм добавит в кэш, так как они все различные. Когда случается промах, алгоритм среди значений в кэше и только что обработанного результата вытесняет то, которое в последующих запросах встречается первый раз как можно позже или не встречается совсем. При таком выборе, следующий кэш промах случится не менее чем через <tex>k</tex> запросов. Предположим, что это не так, и кэш промах случился через <tex>m < k</tex> запросов. Так как количество различных запросов на 1 больше размера кэша, то этот промах произошёл на запросе, который мы вытеснили из кэша в предыдущий раз. Из <tex>m < k</tex> следует, что есть запросы, которые мы не встретили среди первых <tex>m</tex>, а значит их первое вхождение будет после того значения, которое мы вытеснили. Получили противоречие, а значит предположение не верно. Оценим время работы возможно оптимального оффлайн алгоритма <tex>T_\text{mopt} \leqslant k + \lceil\frac{n-k}{k+1}\rceil \leqslant \frac{n}{k}</tex>. Последнее неравенство выполнено, т.к. <tex>n >> \gg k</tex>. Очевидно <tex>T_\text{opt}(\sigma_n) \leqslant T_\text{mopt}(\sigma_n)</tex>, откуда <tex>T_\text{opt}(\sigma_n) \leqslant \frac{n}{k}</tex>
<tex>T_\text{det}(\sigma_n) = n = k \cdot \frac{n}{k} \geqslant k \cdot T_\text{opt}(\sigma_n) \Rightarrow T_\text{det}(\sigma_n) \geqslant k \cdot T_\text{opt}(\sigma_n) + 0</tex>
Теорема доказана.
