Изменение размера оптимальной схемы при переходе к другому базису

Материал из Викиконспекты
Перейти к: навигация, поиск
Эта статья находится в разработке!

Определение

Размер схемы - количество функциональных элементов, необходимое для построения этой схемы. Схемная сложность функции [math]f[/math] относительно базиса [math]B[/math](обозначается [math]SIZEb(f)[/math]) - минимальный размер схемы, вычисляющей функцию [math]f[/math], собранной из функциональных элементов, принадлежащих базису [math]B[/math].

Теорема

Для любых базисов [math]B1[/math], [math]B2[/math] и функции [math]f[/math] [math]SIZEb1(f)[/math] = [math]O(SIZEb2(f))[/math]

Доказательство