Изменения

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

1518 байт добавлено, 19:40, 4 сентября 2022

м

rollbackEdits.php mass rollback

== Доказательство ==

Будем считать, что

<tex>A=k^2</tex> и <tex>\nu = 1/k </tex>.

<tex>\mu = k ^{-5},\; \delta = \dfrac{1}{3}k^{-5}, \; \delta_F = \dfrac{2k}{k^2 - 1} </tex>

Тогда получим, что

<tex> t_f = 3d - 20 </tex> и <tex>\alpha(t_f) = \omega(t_f) = d - 6 </tex>, где <tex>d = \log N/\log k </tex>.

<tex> \varepsilon_B \le \dfrac{1}{4}k^{-4} \cdot \dfrac{4k-1}{4k} </tex>

<tex> \varepsilon_F \le \dfrac{1}{4}k^{-4} \cdot\dfrac{4k-1}{4k} </tex>

<tex> \varepsilon^* = 2^{-39}\sqrt{1 + 79\ln 2} < 2 ^{-36} </tex>

<tex> f > 2^{34} \cdot \dfrac{1-2^{-12}}{1 - 2^{-36}} > 1.7 \times 10^{10} </tex>

<tex> \varepsilon_B = 2 ^{-29}\sqrt{1 + 59\ln 2} < 1.25 \times 10 ^{-8} </tex>

<tex> \delta_F = 128/4095 </tex>

<tex> \varepsilon_F = 1/(8\times 10^7) = 1.25 \times 10^{-8} </tex>

<tex> \sqrt{\dfrac{2(1+\ln m)}{m}} \le k ^{-6} </tex>

<tex> \log k = (\dfrac{1}{12} + o(1))\log M </tex> <tex> M \to \infty </tex>

<tex> f \ge (1 + o(1))\dfrac{m}{2k^4} \ge (1+o(1))k^8\ln k </tex>

<tex>M \to \infty </tex>

<tex> \varepsilon_B = k^{-6}, \; \delta_F = \dfrac{2k}{k^2 - 1}, \; \varepsilon_F = k^{-8} </tex>

<tex> \sqrt{\dfrac{2(1+\ln m)}{m}} \le \dfrac{1}{5}k^{-4} </tex>

<tex> \log k = (\dfrac{1}{8} + o(1))\log M </tex>

<tex> \sqrt{\dfrac{2(1 + \ln \lfloor M^{3/2}\rfloor)}{\lfloor M^{3/2}\rfloor}} \le k^{-6} </tex>

<tex> \varepsilon_B = \dfrac{1}{5}k^{-4}, \; \delta_F = \dfrac{2k}{k^2 - 1}, \; \varepsilon_F = \dfrac{1}{5}k^{-4} </tex>

1632

правки