Изменения

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

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

924 байта добавлено, 16:39, 16 мая 2015
Анализ сети
<tex>(\frac{1}{k} + \frac{\mu\delta kA^2}{1 - \delta^2k^2A^2})c(i,t)</tex>
 
 
<tex> \frac{1}{k}(Nk^{-i} - c(i,t)) </tex>
 
 
<tex> \sum\limits_{j\ge 1} k^{2j-1}\mu\delta^{2j-1}c(i+2j, t) </tex>
 
 
<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}Kk^{-i}</tex>
 
 
лемма 4.2
 
<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)c(i,t)</tex>
 
 
<tex>c=c(i, t), \quad a=a(i,t),\quad \pi=\pi(i,t), \quad \chi=\chi(i, t) </tex>
 
 
<tex>\Delta_1 = \frac{\mu\delta kA^2}{1-\delta^2k^2A^2}c</tex>
 
 
<tex>\Delta_2 = \frac{\nu}{1 - \delta^2k^2A^2}c</tex>
 
 
<tex> \Delta =
\begin{cases}
\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) $$вфы$$ i = \alpha(t) > \alpha(t + 1), t \ge 2$,}
\end{cases}
</tex>
== Конструкция разделителей ==
264
правки

Навигация