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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 6: Строка 6:
  
 
==Теорема==
 
==Теорема==
Для любых базисов <math>B_1</math>, <math>B_2</math> и функции <math>f</math> <math>SIZE_B_1(f)</math> = <math>O(SIZE_B_2(f))</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

Эта статья находится в разработке!

Определение

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

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