Изменения
Нет описания правки
* '''Блок D''' {{---}} мультиплексор, получающий на вход все <tex>f(x_1, x_2, ..., x_k, \sigma_{k + 1}, \sigma_{k + 2}, ..., \sigma_n)</tex> и параметры функции <tex>x_{k + 1}, x_{k + 2}, ..., x_n</tex> в качестве двоичного представления числа. '''''Результат работы схемы''''' {{---}} вывод мультиплексора.
Положим <tex>s = [\lfloor n - 2\log_2 n]\rfloor</tex>; <tex>k = [\lfloor\log_2 n]\rfloor</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}{n^2} = \frac{2^n}{n}</tex>
