22.Сложность вычислений

В реальных вычислениях важно не только то, что функция вычислима (имеется вычисляющая ее процедура), но не менее существенно – какова ее сложность вычисления (зависящая от внутренней сложности функции), а также – можно ли найти наилучшую программу для ее вычисления. Эти вопросы относятся к теории сложности вычислений.

Теорема Блюма об ускорении показывает, что существуют вычислимые функции, не имеющие «наилучшей программы». Но есть класс функций, для которых существует быстро работающая программа, вычисляющая функцию, совпадающую с данной почти всюду.

Может оказаться, что достаточно простая программа, с помощью которой решается некоторая массовая задача, может привести к большому объему вычислений. Следовательно, полезно ввести понятие сложность вычислений. К примеру, под сложностью алгоритмов теории чисел понимается количество арифметических операций (сложений, вычитаний, умножений и делений без остатка), необходимых для выполнения всех действий, предписанных алгоритмом.

Таким образом, следует различать три типа понятия «сложность»:

• Сложность задания (описания) объекта.

• Сложность вычисления (функционирования).

• Конструктивно-энергетическая сложность.

Последнее понятие сложности связано с намерением измерять сложность посредством энергетических затрат. Очевидно, здесь просматривается инженерно-физический подход, связанный с физической реализацией, построением, созданием объекта, сложность которого определяется.