16
правок
Изменения
Нет описания правки
Посчитаем матожидание количества промахов на фазе <tex>i</tex>. Оно максимально, когда в фазе сначала идут новые значения, а потом старые, потому что тогда каждое новое значение имеет шанс вытеснить старое, и при обращении к нему случится кэш промах. Так как на начало фазы <tex>i</tex> в кэше хранятся только значения фазы <tex>i-1</tex>, то понятно, что все новые запросы фазы <tex>i</tex> приведут к кэш промаху. Рассмотрим <tex>j</tex>-й среди старых запросов. Посмотрим на те значения фазы <tex>i-1</tex>, которые к текущему моменту были вытеснены или помечены. <tex>j-1</tex> старых значений пометили сами себя, потому что они были в предыдущей фазе, а <tex>m_i</tex> пометить себя не могли, а поэтому вытеснили случайное подмножество из остальных <tex>k - (j-1)</tex>. Возможно они вытеснили кого-то из первых <tex>j-1</tex> старых значений, которые при обработке вытеснили кого-то другого. Главное, что распределение это не меняет. Вероятность того, что <tex>j</tex>-й старый запрос приведёт к кэш промаху, равена тому, что он был вытеснен из кэша <tex>P_j = \frac{m_i}{k - (j - 1)}</tex>.
В итоге, матожидание времени работы алгоритма не превосходит суммы матожиданий кэш промахов на каждой фазе, которое мы ограничили сверху суммой <tex>m_i</tex>и матожиданием промахов на старых значениях.
<tex>
\begin{align}
E(T_\text{rnd}) &= \leqslant \sum\limits_{i}\left(m_i + \sum\limits_{j}E(\text{кэш промах на}\; j)\right) = \\
&= \sum\limits_{i}\left(m_i + \sum\limits_{j=1}^{k-m_i}\frac{m_i}{k-j+1}\right) = \sum\limits_{i}m_i\left(1 + \sum\limits_{j=1}^{k-m_i}\frac{1}{k-j+1}\right) = \\
&= \sum\limits_{i}m_i\left(1 + \sum\limits_{j=m_i+1}^{k}\frac{1}{j}\right) = \sum\limits_{i}m_i(1 + H_k - H_{m_i+1}) \geqslant leqslant \sum\limits_{i}m_iH_k = H_k\sum\limits_{i}m_i
\end{align}
</tex>
