Изменения

Перейти к: навигация, поиск

Сортирующая сеть O(log N)

541 байт добавлено, 17:06, 16 мая 2015
Анализ сети
<tex> \sum\limits_{j\ge 1} (k\delta)^{2j-1}c(i+2j, t) = c(i,t)\sum\limits_{j\ge 1} (k\delta)^{2j-1}A^{2j} < c(i,t)\frac{\delta k A^2}{1-\delta^2k^2A^2} </tex>
<tex>\frac{1}{k}KkNk^{-i}</tex>
\Delta_1,&\text{ $i = \alpha(t) < \alpha(t+1)$,}\\
\Delta_2,&\text{ $i = \omega(t) < \omega(t+1)$,}\\
\Delta_1 + \Delta_2,&\text{если $\alpha(t) <i < \omega(t) $$вфы$$ \quad ||\quad i = \alpha(t) > \alpha(t + 1), t \ge 2$,}
\end{cases}
</tex>
 
 
<tex>(k - 1)\Delta - \frac{1}{2}\pi \le (k - 1)\Delta_1 + \frac{A\nu k - 2A\nu + 1}{2A^2k^2}c </tex>
 
 
лемма 4.3
 
<tex> \varepsilon^* \le \frac{\mu}{k},</tex>
 
<tex>(\mu + (k - 1)\frac{\mu\delta k A^2}{1 - \delta^2k^2A^2} + \frac{A\nu k - 2A\nu + 1}{2k^2A^2} + \varepsilon_B)\frac{1}{A\nu} + \mu\delta\frac{Ak}{\nu} \le \mu </tex>
 
Лемма 4.4
 
<tex>\mu \le \frac{\nu}{Ak^2}, </tex>
 
 
<tex>\mu\le\frac{1}{2}\delta_F\frac{A\nu k - 1}{A^2k^2},</tex>
 
 
<tex>\varepsilon_F\frac{1}{A\nu} + \delta^2\frac{Ak}{\nu} \le \delta </tex>
== Конструкция разделителей ==
264
правки

Навигация