Математическая логика и теория алгоритмов. Стенюшкина В.А. - 65 стр.

       3 Сложность алгоритмов
       3.1 Характеристики сложности вычислений

       Сложность алгоритма (СА) – величина, характеризующая длину описания
 или громоздкость процессов его применения к исходным данным /8/.
       Сложность описания алгоритма зависит от выбора того или иного спосо-
ба задания алгоритмов. Если такой способ зафиксирован, то СА обычно пони-
мают как длину записи, количество встречающихся в ней выражений опреде-
ленного типа и т. п. Например, под сложностью описания машины Тьюринга
понимают общее число символов внешнего и внутреннего алфавитов, или число
команд в программе данной машины. Сложность нормального алгоритма пони-
мают как длину слова, полученного записыванием друг за другом всех формул
подстановки в том порядке, как они встречаются в схеме данного алгоритма
(между формулами помещается специальный символ). Сложность процесса
применения алгоритма к исходным данным называется сложностью вычисле-
ний. Сложность вычислений данного алгоритма есть функция, которая каждому
объекту из области применимости данного алгоритма сопоставляет число, ха-
рактеризующее сложность процесса применения этого алгоритма к данному
объекту. Сложность работы алгоритма характеризуется длительностью алгорит-
мического процесса во времени и объемом промежуточных результатов. Для
машины Тьюринга – это соответственно число тактов работы машины от исход-
ного слова до результата и количество ячеек ленты, в которых хотя бы раз по-
бывал указатель при работе над словом. Для нормальных алгоритмов аналогич-
ными характеристиками является число применений формул подстановки при
работе над исходным словом и максимальная длина слов, появляющихся в про-
цессе применения алгоритма к данному слову.
       В терминах сложности вычислений удается уточнить и исследовать мно-
 гие проблемы нахождения оптимального алгоритма решения конкретных задач.
 Развивается аксиоматический подход к оценке сложности алгоритмов и вычис-
 лений.
       Оценивая сложность различных алгоритмов, следует исходить из некото-
 рой модели исполнителя. Здесь используется модель 1RAM – однопроцессор-
 ная машина с равнодоступной памятью /4/.
       3.2 Размер входа. Время работы
      При исследовании сложности вычислений обычно изучают зависимость
времени работ от размера входа /5/.
      Рассмотрим задачу сортировки.
      Вход: Последовательность n чисел (а1, …, а n).
      Выход: Последовательность n чисел (а1′, …, а′n), являющаяся перестанов-
кой входной последовательности и удовлетворяющая условию: а1′≤ …≤ а′ n.
      Будем называть алгоритм правильным, если на любом допустимом входе
он заканчивает работу и выдает результат, удовлетворяющий условиям задачи
В этом случае будет говорить также, что алгоритм решает данную задачу.