Асимптотические оценки


Теорема: (основная теорема оценки трудоемкости синтеза)

Существует метод синтеза формального представления дискретной функции при котором количество не нулевых коэффициентов разложения M(m) и число операций L(m) необходимых для ее вычисления, удовлетворяют следующим асимптотическим оценкам. Устремим длину характеристического вектора clip_image002.

clip_image004 – число операций, необходимых для вычисления функций.

clip_image006 – объем памяти, необходимый для хранения коэффициентов.

Где m – число переменных, на которые разбивается аргумент функции.

clip_image008

clip_image010

n~logk(m) clip_image012

Замечание:

1. При выводе теоремы использовалась произвольная функционально полная система операции, состоящая из всех известных унарных и бинарных операций.

2. Почти все функции не имеют эффективной программной или аппаратной реализации.

3. Необходимо использовать архитектурное проектирование вычислительных средств с использованием архитектурных принципов заключающихся в декомпозиции обработки данных на части, а так же представление этой декомпозиции в виде блок-схемы. Декомпозиция завершается когда полученные блоки представляют элементы которые могут быть реализованы на практике.