75
правок
Изменения
→Доказательство: поменял вывод оценки
'''''Результат работы схемы''''' - вывод мультиплексора.
Положим <math>s = [n - 52\log_2 n]</math>; <math>k = [3 \log_2 n]</math>. Тогда* <math>L_A \sim 2^{3 \log_2 n} \leq lesssim \frac{2^n}{n}</math>* <math>L_B < sp \cdot 2^s = 2^{k + s} \leq = \frac{2^n}{n}</math>* <math>L_C \sim p \cdot 2^{n - k} = \frac{2^k}{n - 5\log_2 n} \cdot \frac{2^n}{n^3s} \sim \frac{2^n}{n}</math>* <math>L_D \sim 2^{n - k} \leq = \frac{2^n}{n}</math>
Итого, имеем схему с итоговым числом элементов <math>\sim \frac{2^n}{n}</math>, откуда следует, что <math>size_B (f) \lesssim \frac{2^n}{n}</math>, '''ч.т.д.'''
