Изменение размера оптимальной схемы при переходе к другому базису — различия между версиями
Sementry (обсуждение | вклад) м |
Sementry (обсуждение | вклад) м |
||
| Строка 6: | Строка 6: | ||
==Теорема== | ==Теорема== | ||
| − | Для любых базисов <math>B_1</math>, <math>B_2</math> и функции <math>f</math> <math> | + | Для любых базисов <math>B_1</math>, <math>B_2</math> и функции <math>f</math> <math>SIZE_{B_1}(f)</math> = <math>O(SIZE_{B_2}(f))</math> |
==Доказательство== | ==Доказательство== | ||
Версия 05:52, 4 октября 2010
Эта статья находится в разработке!
Определение
Размер схемы - количество функциональных элементов, необходимое для построения этой схемы. Схемная сложность функции относительно базиса (обозначается ) - минимальный размер схемы, вычисляющей функцию , собранной из функциональных элементов, принадлежащих базису .
Теорема
Для любых базисов , и функции =
