Изменения

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

Сортирующая сеть глубины O(log N)

995 байт добавлено, 02:59, 17 мая 2015
Анализ сепараторов
<tex>\dbinom{n}{k}\dbinom{j - fk/2}{k} \le \dbinom{n}{k}\dbinom{j}{k} < \bigg(\dfrac{e^2(f+2)^2n}{k^2}\bigg)^k </tex>
 
<tex> 1 + \sum\bigg(\dfrac{e^2(f+2)^2n}{k^2}\bigg)^k < \dfrac{90}{89} \bigg(\dfrac{e^2(f + 2)^2n}{4j}\bigg) ^{2j/(f+2)} </tex>
 
<tex>e^2nj \ge e^2j > 90 </tex>
 
<tex>x \le 2j/(f+2) </tex>
 
<tex>\dfrac{d}{dx}\ln\bigg(\bigg(\dfrac{e^2nj}{x^2}\bigg)^x\bigg) = \ln\dfrac{nj}{x^2} \ge \ln\dfrac{n(f + 2)^2}{4j} \ge \ln\dfrac{25(f+2)^2}{4f} \ge \ln 90</tex>
 
 
<tex> \dfrac{90}{89} \bigg(\dfrac{e^2(f + 2)^2n}{4j}\bigg) ^{2j/(f+2)} \cdot \dfrac{1 + e^{-5}}{1 - e^{-5}} \Bigg(\bigg(\dfrac{efn}{2\varepsilon_Fj}\bigg)^{2/f}\dfrac{2ej}{fn}\Bigg)^{\varepsilon_Fj} </tex>
 
 
<tex>x = \bigg(\dfrac{e^2(f + 2)^2n}{4j}\bigg) ^{2/\varepsilon_Ff} \cdot \bigg(\dfrac{efn}{2\varepsilon_Fj}\bigg)^{2/f} \cdot \dfrac{2ej}{fn}; </tex>
 
 
<tex>(e^2/\varepsilon_F)^{2/f} = ((e^2/\varepsilon_F)^{\varepsilon_F})^{2/\varepsilon_Ff} \le (e^2))^{2/\varepsilon_Ff} </tex>
 
<tex>x \le \bigg(\dfrac{e^4(f+2)^2n}{4j}\bigg)^{2//\varepsilon_Ff}\bigg(\dfrac{2ej}{fn}\bigg)^{(f-2)/f} </tex>
 
<tex>t = /\varepsilon_F(f-2)/2 </tex>
== Доказательство ==
264
правки

Навигация