264
правки
Изменения
м
<tex>\alpha(t + 1) < \alpha(t)</tex>
<tex>c(\alpha(t), t) = (A/\nu)c(\alpha(t + 1), t + 1) \ge 2Ak^2/\nu</tex>Далее мы будем использовать следующие утверждения
лемма Лемма 3.1 Если <tex>\alpha(i, t) \neq 0</tex> тогда
→Конструкция сети
<tex> a(i, t) </tex> целые.
Чтобы как-то перераспределить провода между временами <tex> Ot</tex> и <tex>t + 1 </tex> каждый узел на уровне i посылает <tex>\pi(i, t) </tex> значений своим родителям и <tex>\log Nchi(i, t) </tex> значений каждому из своих <tex>k</tex> детей. Если <tex> c2 \log_2 N le t < t_f </tex> , то
<tex> \pi(\alpha(t),t) =
</tex>
Отметим, что для все <tex>\pi(i, t)</tex> и <tex>\chi(i, t)</tex> целые: в частности, если <tex>\alpha(t + 1) < \alpha(t)</tex>, то<tex>c(\alpha(t), t) = (A/\nu)c(\alpha(t + 1), t + 1) \ge 2Ak^2/\nu</tex>
Если сепараторы, используемые для построения сети достаточно хорошие, то(мы проверим чуто позже) существует такое целое число <tex>\chigamma </tex>, не превосходящее <tex>\alpha(it_f) </tex>, tно при этом отличающееся от <tex>\alpha(t_f)</tex>не более чем на константу, не зависящую от <tex>N</tex>, такое, что для любого узла <tex>x</tex>, находящегося на уровне <tex>\gamma </tex>, все ключи, являющиеся потомками узла <tex>x</tex> в момент времени <tex>t_f</tex> адресуются толко к ключам, являющимся потомками <tex>x</tex>. Следовательно, построеная сеть может быть дополнена до сортирующей единственным слоем из параллельных сортирующих сетей, каждая из которых будет содержать <tex>k^{d - \gamma} </tex> входных проводов.
\end{cases}
</tex>
ДоказательствоЭто утверждение следует из того
<tex>\sum\limits^d_{j=0} k^ja(j, t) = N </tex>
Непосредственно, когда <tex> i = \alpha(t) </tex>и подставляется
где <tex> c(j, t) = c(i, t)A^{j-i}</tex> когда при <tex>i\ge\alpha(t)+2</tex>.
лемма 3.2 Если <tex>\alpha(t + 1) > \alpha(t) </tex> тогда <tex>\alpha(t) = 0</tex> или <tex>c(\alpha(t),t)\le Ak^2/\nu</tex>
ДоказательствоЕсли <tex>\alpha(t+1) > \alpha(t) > 0</tex> , тогда <tex>\alpha(t) - 1 < \alpha^*(t + 1) </tex> , а значит и <tex>c(\alpha(t),t) < 2Ak^2/\nu</tex>.
== Мусор ==
