75
правок
Изменения
→Доказательство: расписываем вывод
Положим <tex>s = [n - 2\log_2 n]</tex>; <tex>k = [\log_2 n]</tex>. Тогда число элементов в блоках
* <tex>L_A = O(2^k) = O(2^{\log_2 n}) = O(n)</tex>
* <tex>L_B \leq (s - 1) \cdot (t(1) + t(2) + ... + t(p)) < sp \cdot 2^s = n \cdot \frac{2^n}{k + sn^2} = \frac{2^n}{n}</tex>
* <tex>L_C = O(p \cdot 2^{n - k}) = O\left(\frac{p}{n} \cdot 2^n\right) = O\left(\frac{2^n}{s}\right) = O\left(\frac{2^n}{n - 2\log_2 n}\right)</tex>
* <tex>L_D = O(2^{n - k}) = O\left(\frac{2^n}{n}\right)</tex>
