5.4. Характеристики сложности вычислений
В общей теории алгоритмов изучаются лишь принципиальная возможность алгоритмического решения задачи. При рассмотрении конкретных задач не обращается внимания на ресурсы времени и памяти для соответствующих им разрешающих алгоритмов.
Однако нетрудно понять, что принципиальная возможность алгоритмического решения задачи еще не означает, что оно может быть практически получено. Поэтому возникает потребность уточнить понятие алгоритмической разрешимости, введя характеристики сложности алгоритмов, позволяющие судить об их практической реализуемости.В качестве модели вычислительного устройства выберем МТ. Пусть МТ вычисляет функцию f(x). Определим функцию tT(x), равную числу шагов машины Т, выполненному при вычислении f(x), если f(x) определено. Если f(x) не определено, то значение tT(x) считается неопределенным. Функция tT(x) называется временной сложностью.
Активной зоной при работе машины Т на слове х называется множество всех ячеек ленты, которые либо содержат непустые символы, либо посещались в процессе вычисления f(x) устройством машины Т. Определим функцию sT(x), равную длине активной зоны при работе машины Т на слове х, если f(x) определено. Если f(x) не определено, то значение ST(x) считается неопределенным. Функция ST(x) называется емкостной (ленточной) сложностью.
Введенные функции ST(x) и tT(x) являются словарными.
Удобно ввести для рассмотрения функции натурального аргумента
Они также называются функциями временной и емкостной
сложности (по худшему случаю).
Еще по теме 5.4. Характеристики сложности вычислений:
- 6.10. Вычисление теплоемкостей cv и cp, сравнение вычисленных значений с опытными
- 2.6. Линейная сложность
- Возросшая сложность и скорость
- § 5. Сложность, упорядоченность; организация, информация
- Сложность
- Закон возрастания сложности систем
- Синергетика как теория сложности Synergetics as the theory of complexity
- Когнитивный стиль лидеров. Концепция «интегративной сложности»
- 4-6. Различия в сложности монемных структур
- § 35. Две ступени семантической сложности простого предложения
- 5.5. Классы сложности задач
- Своеобразие и сложность практики разгосударствления собственности в российских условиях
- 3. 1. Скорость эволюции и сложность организмов
- Сложность понимания христианской парадигмы
- § 1. Динамика и сложность социальных форм
- Алгоритм разграничения однородности и сложности
- 5. Сложность реальных языковых ситуаций
- Сложность как процесс Complexity as a Process
- Сложности подсчета показателей дохода и продукта. Проблема оценки благосостояния нации
- От простоты к сложности: постнеклассическая революция в науке From simplicity to complexity:postnonclassical revolution in science