Метод синтеза

Схема S для функции f (x₁, …, x_n), заданной таблицей 1, строится на основе её представления (6) и состоит из 6 блоков (рис. 6):

1) Блок А реализует Q (x ,…,x ), причем L(A)£(n-k) 2 .

2) Блок B реализует Q (x ,…,x ), причем L(B) £k 2 .

3) Блок C реализует все различные функции f (s₁,…, s , ), тогда L(С) £p S 2 .

4) Блок D реализует все функции = , тогда L(D) £ p 2 .

5) Блок G осуществляет умножение , поэтому L(G)=2

6) Наконец, блок F реализует функцию f(x₁, …, x_n) как дизъюнкцию функций, реализованных блоком G. L(F) £ 2 .

S:

Рис. 6

Итак, L(S) = L(A)+L(B)+L(C)+L(D)+L(G)+L(F)£(n-k)* 2 + k*2 +
+p*S*2 + p* 2 +2 = (n-k+1)* 2 +k*2 + p*S*2 + p* 2 =

= (n-k+1)*2 +k*2 +p*(2 +S*2 )£(n-k+1)*2 +k*2 +( +1)*(2 + S*2 ).

Положив k = [3 log n], s = [n-5 log n] получим L(S) £ (1 + O()) и L(n) £ (1 + O()). Теорема полностью доказана.

~

Теорема 4 (без доказательства). L(n) > .

Теорема 5 (как следствие теорем 3 и 4). L(n) ~ .

Замечание. Описанный метод синтеза в теореме 3 является асимптотически наилучшим.