689
правок
Изменения
м
Нет описания правки
==Теорема==
Для любых базисов <math>~B_1</math>, <math>~B_2</math> и функции <math>~f</math> верно равенство <math>~size_{B_1B_2}(f) \leq C_{(B_1,\;B_2)}size_{B_2B_1}(f)</math>
==Доказательство==
Пусть базис <math>~B_2</math> состоит из функций <math>~g_1, g_2, ..., g_n</math>. Схемная сложность функции <math>~g_i</math> относительно базиса <math>~B_1</math> равна <math>~size_{B_1}(g_i)</math>. Иначе говоря, каждый функциональный элемент базиса <math>~B_2</math> мы собираем с помощью элементов из базиса <math>~B_1</math>. Тогда понятно, что в сумме мы затратим не более чем в <math>~C = \max_{i=1}^n size_{B_1}(g_i)</math> раз больше функциональных элементов, и <math>~C</math> зависит от выбранных базисов, но не зависит от формулы.
