Изменения

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

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

203 байта добавлено, 15:24, 16 мая 2015
Нет описания правки
}}
Эти идеальные разделители могут быть использованы как модули для построения сортирующей сети на <tex>N</tex> входов, где <tex>N = k^d</tex> для некоторого положительного числа d. Такая сеть будет представлять собой композицию сетей <tex>N_0, N_1, N_2 .. N_{d-1}</tex>, где <tex>N_t</tex> – парраллельная композиция <tex>k^t</tex> идеальных разделителей одинакового размера.
 
== Конструкция сети ==
<tex>\alpha^*(t) = \frac{t\log \frac{1}{\nu} - \log N + \log(2A\nu k^3)}{\log A}</tex>
<tex>c(\alpha(t),t) < 2Ak^2/\nu</tex>
 
== Анализ сети ==
 
== Конструкция разделителей ==
 
== Анализ сепараторов ==
 
== Доказательство ==
264
правки

Навигация