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

Материал из Викиконспекты
Версия от 05:46, 4 октября 2010; Sementry (обсуждение | вклад) (Новая страница: «{{В разработке}} ==Определение== Размер схемы - количество функциональных элементов, необхо…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Эта статья находится в разработке!

Определение

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

Теорема

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

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