264
правки
Изменения
→Анализ сепараторов
<tex> \dfrac{1 + e^{-5}}{1 - e^{-5}} \Bigg(\bigg(\dfrac{efn}{2\varepsilon_Fj}\bigg)^{2/f}\dfrac{2ej}{fn}\Bigg)^{\varepsilon_Fj}</tex>
<tex> p(s) \le \dbinom{n}{s} \bigg(\dfrac{ejs}{(\tfrac{1}{2}fs + \varepsilon_Fj)n}\bigg)^{\tfrac{1}{2}fs+\varepsilon_Fj} </tex>
<tex> p(s) \le \dbinom{n}{s} \bigg(\dfrac{es}{\varepsilon_Fn}\bigg)^{\varepsilon_Fj} </tex>
<tex> p(s) \le \dbinom{n}{s} \bigg(\dfrac{2ej}{fn}\bigg)^{fs/2} </tex>
<tex> g(x) =
\begin{cases}
\bigg(\dfrac{en}{x}\bigg)^x \bigg(\dfrac{ex}{\varepsilon_Fn}\bigg)^{\varepsilon_Fj} &\text{если $x \le \varepsilon_F\cdot2j/f$}\\
\bigg(\dfrac{en}{x}\bigg)^x \bigg(\dfrac{2ej}{fn}\bigg)^{fx/2} &\text{если $x \ge \varepsilon_F\cdot2j/f$}
\end{cases}
</tex>
<tex> \sum\limits_{s-1}^n q(s) \le \dfrac{1 + e^{-5}}{1 - e^{-5}} g(\varepsilon_F\cdot2j/f) </tex>
<tex> x \le \varepsilon_F\cdot2j/f </tex>
<tex> \dfrac{d}{dx}\ln g(x) = \ln\dfrac{n}{x} + \dfrac{\varepsilon_Fj}{x} \ge \dfrac{1}{2}f \ge 5 </tex>
<tex> x \ge \varepsilon_F\cdot2j/f </tex>
<tex> \dfrac{d}{dx}\ln g(x) = \ln\dfrac{n}{x} + \dfrac{1}{2}f\ln\dfrac{2ej}{fn} \\ \le \ln\dfrac{e}{\varepsilon_F} + \left(\dfrac{1}{2}f - 1\right)\ln\dfrac{2ej}{fn} \\ \le \ln\dfrac{f}{4} + \left(\dfrac{1}{2}f - 1\right)\ln\dfrac{2e}{25} \\ <-5</tex>
<tex> \delta = e ^{-5}, b=\varepsilon_F\cdot 2j/f, a= \lfloor b\rfloor, c = a + 1</tex>
<tex> \sum\limits_{s=1}^n g(s) = \sum\limits_{s=1}^a g(s) + \sum\limits_{s=c}^n g(s) \\ < \dfrac{1}{1-\delta}(g(a) + g(c)) \\ \le \dfrac{\delta^{b-a} + \delta^{c-b}}{1-\delta}g(b) \\ \le \dfrac{1 + \delta}{1-\delta}g(b) </tex>
== Доказательство ==
