264
правки
Изменения
→Конструкция разделителей
== Конструкция разделителей ==
<tex>M \ge 32A^2k^2 </tex>
<tex>a=mn, \quad M/32 < m \le M/16 </tex>
<tex>|F_j|=fn,\quad|B_j|=bn</tex>
<tex>|F_j|=2^s f_0,\quad|B_j|=2^s b_0</tex>
<tex>2f_0+kb_0 < 2A^2k62 :</tex>
<tex>i=\alpha(t) < \alpha(t+1) </tex>
<tex>f_0 = 0, \qquad b_0=1, \qquad 2^s = \dfrac{a(i,t)}{k}, </tex>
<tex>i=\alpha(t) > \alpha(t+1) </tex>
<tex>f_0 = \dfrac{k}{2}, \qquad b_0=\dfrac{Ak}{\nu} -1, \qquad 2^s = \dfrac{\nu c(i,t)}{Ak^2}, </tex>
<tex>\alpha(t) < i < \omega(t) </tex>
<tex>f_0 = A\nu k - 1, \qquad b_0=2A^2k - 2A\nu, \qquad 2^s = \dfrac{c(i,t)}{2A^2k^2}, </tex>
<tex>i=\omega(t) < \omega(t + 1) </tex> <tex>t\ge 2</tex>
<tex>f_0 = A\nu k - 1, \qquad b_0=2A^2k\dfrac{Nk^{-i}}{c(i,t)} - 2A\nu, \qquad 2^s = \dfrac{c(i,t)}{2A^2k^2}, </tex>
<tex>i=\omega(t) < \omega(t + 1) </tex>
<tex>c(i,t) = c(i+1,t+1)/A\nu < AkN^{-i}/\nu</tex>
<tex>m_0 = 2f_0 + kb_0 </tex>
<tex>a 2^s m_0</tex>
<tex>m_0 < M/16</tex>
<tex> 2^r m_0 \le M/16 </tex>
<tex> m=2^r m_0, n = a/m, f = 2^r f_0, b = 2^r b_0 </tex>
<tex>f \ge \dfrac{\nu}{2Ak} \cdot \dfrac{A\nu k - 1}{A\nu k - \dfrac{\nu}{Ak}}m </tex> где <tex> f \neq 0</tex>
Теорема 5.1
<tex>m\ge 100, n\ge 16, f\ge 10 </tex>
<tex> m = 2f + kb </tex>
<tex> \varepsilon_B \ge \sqrt{\dfrac{2(1 + \ln m)}{m}} </tex>
<tex> \delta_F \le 1/25 </tex>
<tex> \varepsilon_F \ge \dfrac{2}{f - 2}\left (1 + \dfrac{\ln(3e^5f)}{\ln(0.12/e\delta_F)}\right )</tex>
== Анализ сепараторов ==
== Доказательство ==
