1632
правки
Изменения
м
rollbackEdits.php mass rollback
<tex>|F_j|=fn,|B_j|=bn</tex>
== Анализ сепараторов разделителей ==лемма 6.3<tex> p = \dfrac{1}{kn}\sum\limits _{i=1}^k r_i </tex> <tex>\sum\limits_{i=1}^k|R_i\cap S| \ge (p+t)ks </tex> <tex> \Bigg( \bigg( \dfrac{p}{p+t} \bigg) ^{p+t} \bigg(\dfrac{1-p}{1-p-t}\bigg)^{1-p-t}\Bigg)^{ks} </tex> <tex> \bigg( \dfrac{p}{p+t} \bigg) ^{p+t} \bigg(\dfrac{1-p}{1-p-t}\bigg)^{1-p-t} < \exp(-2t^2) </tex> <tex> \bigg( \dfrac{p}{p+t} \bigg) ^{p+t} \bigg(\dfrac{1-p}{1-p-t}\bigg)^{1-p-t} < \bigg(\dfrac{ep}{p+t}\bigg) ^{p+t} </tex> <tex> \exp(-2t^2ms) \le (em)^{-n^2/s} \le (em)^{-n} </tex> <tex> \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> p(s) \le \dbinom{n}{s} \bigg(\dfrac{ejs}{(\tfrac{1}{2}fs + \varepsilon_Fj)n}\bigg)^{\tfrac{1}{2}fs+\varepsilon_Fj} </tex> <tex> p(s) \le \dbinom{n}{s} \bigg(\dfrac{es}{\varepsilon_Fn}\bigg)^{\varepsilon_Fj} </tex> <tex> p(s) \le \dbinom{n}{s} \bigg(\dfrac{2ej}{fn}\bigg)^{fs/2} </tex> <tex> g(x) =\begin{cases}\bigg(\dfrac{en}{x}\bigg)^x \bigg(\dfrac{ex}{\varepsilon_Fn}\bigg)^{\varepsilon_Fj} &\text{если $x \le \varepsilon_F\cdot2j/f$}\\\bigg(\dfrac{en}{x}\bigg)^x \bigg(\dfrac{2ej}{fn}\bigg)^{fx/2} &\text{если $x \ge \varepsilon_F\cdot2j/f$}\end{cases}</tex> <tex> \sum\limits_{s-1}^n q(s) \le \dfrac{1 + e^{-5}}{1 - e^{-5}} g(\varepsilon_F\cdot2j/f) </tex> <tex> x \le \varepsilon_F\cdot2j/f </tex> <tex> \dfrac{d}{dx}\ln g(x) = \ln\dfrac{n}{x} + \dfrac{\varepsilon_Fj}{x} \ge \dfrac{1}{2}f \ge 5 </tex> <tex> x \ge \varepsilon_F\cdot2j/f </tex> <tex> \dfrac{d}{dx}\ln g(x) = \ln\dfrac{n}{x} + \dfrac{1}{2}f\ln\dfrac{2ej}{fn} \\ \le \ln\dfrac{e}{\varepsilon_F} + \left(\dfrac{1}{2}f - 1\right)\ln\dfrac{2ej}{fn} \\ \le \ln\dfrac{f}{4} + \left(\dfrac{1}{2}f - 1\right)\ln\dfrac{2e}{25} \\ <-5</tex> <tex> \delta = e ^{-5}, b=\varepsilon_F\cdot 2j/f, a= \lfloor b\rfloor, c = a + 1</tex> <tex> \sum\limits_{s=1}^n g(s) = \sum\limits_{s=1}^a g(s) + \sum\limits_{s=c}^n g(s) \\ < \dfrac{1}{1-\delta}(g(a) + g(c)) \\ \le \dfrac{\delta^{b-a} + \delta^{c-b}}{1-\delta}g(b) \\ \le \dfrac{1 + \delta}{1-\delta}g(b) </tex> <tex> \dfrac{90}{89} \bigg(\dfrac{e^2(f + 2)^2n}{4j}\bigg) ^{2j/(f+2)} </tex> <tex>s_1,\; s_1,+s_2, \; s_1+s_2+s_3, \; \dots ,\; s_1+s_2+s_3+\dots +s_k </tex> <tex> \sum\limits_{i = 1}^{k}(s_i+dfrac{1}{2}f) \le j, </tex> <tex> \sum\limits_{k=0}^n\dbinom{n}{k}\dbinom{j - fk/2}{k} </tex> <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> <tex> x^{f/(f-2)} \le 0.24\Bigg(\dfrac{e^5(f+2)^2}{0.48f}\bigg(\dfrac{ej}{0.12fn}\bigg)^{t-1}\Bigg)^{1/t} \\ \le 0.24\Bigg(3e^5f\bigg(\dfrac{e\delta_F}{0.12}\bigg)^{t-1}\Bigg)^{1/t} </tex> <tex> t-1 \ge \dfrac{\ln(3e^5f)}{\ln(0.12/e\delta_F)} </tex> <tex> x^{f/(f-2)} \le 0.24 </tex> <tex>x <0.32 </tex> <tex> 1.025 \sum\limits_{i\ge1} 0.32^i </tex>
== Доказательство ==
Будем считать, что
<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> M/32 < m \le M/16 </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>
