ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 14.02.2021
Просмотров: 113
Скачиваний: 1
Сложность
алгоритмов
.
Принято
рассматривать
сложность
алгоритма
с
двух
точек
зрения
:
как
величину
,
характеризующую
длину
описания
алгоритма
и
как
трудоемкость
процесса
применения
алгоритма
к
исходным
данным
.
Сложность
описания
алгоритма
зависит
от
выбора
того
или
иного
способа
задания
алгоритмов
.
Под
сложностью
описания
машины
Тьюринга
обычно
понимают
число
ее
внутренних
состояний
и
внешних
символов
.
Сложность
нормального
алгорифма
определяется
как
длина
его
изображения
,
т
.
е
.
длина
слова
,
полученного
выписыванием
друг
за
другом
всех
формул
подстановки
в
порядке
,
в
каком
они
встречаются
в
схеме
данного
алгоритма
,
причем
между
формулами
вставляется
специальная
разделительная
буква
.
Сложность
процесса
применения
алгоритма
к
исходным
данным
называется
сложностью
вычислений
.
Сложность
вычисления
алгоритма
есть
функция
,
сопоставляющая
каждому
объекту
из
области
применимости
данного
алгоритма
число
,
характеризующее
сложность
процесса
применения
алгоритма
к
данному
объекту
.
Такая
функция
называется
сигнализирующей
.
Наиболее
важные
характеристики
сложности
работы
алгоритма
–
длительность
алгоритмического
процесса
во
времени
и
объем
промежуточных
результатов
.
Для
машины
Тьюринга
сигнализирующая
времени
–
число
тактов
работы
машины
при
преобразовании
исходного
слова
в
результат
;
сигнализирующая
памяти
(
или
емкости
) –
количество
ячеек
ленты
,
в
которых
хотя
бы
раз
побывала
головка
машины
Тьюринга
при
работе
над
исходным
словом
.
Для
нормальных
алгорифмов
сигнализирующая
времени
–
число
применений
формул
подстановки
при
работе
данного
алгоритма
над
исходным
словом
;
сигнализирующая
емкости
–
максимальная
длина
слов
,
появляющихся
в
процессе
применения
алгоритма
к
данному
слову
.