Характеристики сложности вычислений

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

В качестве модели вычислительного устройства выберем МТ. Пусть МТ вычисляет функцию f(x). Определим функцию t_T(x), равную числу шагов машины Т, выполненному при вычислении f(x), если f(x) определено. Если f(x) не определено, то значение t_T(x) считается неопределенным. Функция t_T(x) называется временной сложностью.

Активной зоной при работе машины Т на слове х называется множество всех ячеек ленты, которые либо содержат непустые символы, либо посещались в процессе вычисления f(x) устройством машины Т. Определим функцию s_T(x), равную длине активной зоны при работе машины Т на слове х, если f(x) определено. Если f(x) не определено, то значение S_T(x) считается неопределенным. Функция S_T(x) называется емкостной (ленточной) сложностью.

Введенные функции S_T(x) и t_T(x) являются словарными.

Удобно ввести для рассмотрения функции натурального аргумента

Они также называются функциями временной и емкостной

сложности (по худшему случаю).

Дата добавления: 2014-01-15