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

5.1. Понятие о сложности вычислений

Как указано в главе 1, одним из основных вопросов теории алгоритмов является следующий: как быстро можно решить задачу и какая память для этого нужна? Для ответа на него необходимо рассмотреть следующие вопросы.

1. Как оценить качество алгоритма?

2. Что такое эффективный алгоритм?

3. Как эффективно решить данную проблему?

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

Для оценки алгоритмов существует много критериев.

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

Чаще всего нас интересует порядок роста необходимых для решения задачи времени и емкости памяти при увеличении входных данных.

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

Под емкостной сложностью понимают объем памяти, требуемой для выполнения программы.

Нужно учитывать следующие моменты.

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

Во-вторых, бывает важно знать, как изменяется время работы программы при увеличении размерности задачи. Это позволит оценить объем исходных данных, которые могут быть обработаны на компьютере за приемлемое время.

Реальное время работы программы на компьютере зависит не только от выбранного алгоритма. В значительной степени оно определяется типом ЭВМ, структурой представления данных, программной реализацией.

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

5.2 Машина с произвольным доступом к памяти

Машина с произвольным доступом к памяти (Random Access Machine, RAM) или равнодоступная адресная машина (РАМ) моделирует вычислительную машину с одним сумматором, в которой команды программы не могут изменять сами себя.

РАМ состоит из входной ленты, с которой она может только считывать, и выходной ленты, на которую она может только записывать и памяти (рисунок 5.1).

Рисунок 5.1 – Машина с произвольным доступом к памяти

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

Имеется устройство, которое хранит программу, т.е. последовательность команд. Память – это последовательность подряд пронумерованных ячеек (регистров), каждая из которых способна хранить двоичную запись произвольного целого числа. Обращение к значению c(i), хранимому в некотором регистре, осуществляется по адресу (номеру) этого регистра. Регистр с номером 0 (r₀) называется сумматором или аккумулятором, в нем производятся все вычисления. При рассмотрении РАМ могут быть выбраны любые наборы команд. В качестве системы команд будем использовать стандартный набор команд, приведенный в таблице 5.1. Машина является одноадресной, каждая команда состоит из двух частей – кода операции и операнда.

Операнд команды может быть одного из следующих типов:

1) =і означает само целое число і и называется литералом (непосредственная адресация), т.е. значение операнда v(=i) равно i;

2) і – содержимое регистра і (прямая адресация), т.е. v(i) = c(i);

3) *і означает косвенную адресацию, т.е. значением операнда служит содержимое регистра j, где j – целое число, находящееся в регистре i; если j<0, машина останавливается, т.е.  v(*i) = c(c(i)).  

Счетчик команд – это переменная, принимающая значение из множества неотрицательных целых чисел. В начале счетчик команд установлен на первую команду программы.  после выполнения і-той команды либо счетчик увеличивает свое значение на 1 (т.е. выполняется следующая команда), либо его значение определяется специальной командой перехода.

 Набор команд РАМ традиционен для ассемблеров реальных ЭВМ и состоит из команд считывания и запоминания, арифметических и логических команд, команд перехода, команд ввода и вывода и команды останова.

Существенным является то, что при выполнении всякой команды результат этого выполнения содержится в сумматоре.

Арифметические команды РАМ.

Во всех арифметических командах в операнде могут присутствовать все типы адресации. 

ADD a – сложение.

К содержимому сумматора прибавляется значение операнда а:

 c(0) := c(0) + v(a).

SUB a – вычитание.

От содержимого сумматора отнимается значение операнда а:

 c(0) := c(0) – v(a).

MULT a – умножение.

Содержимое сумматора умножается на значение операнда а:

 c(0) := c(0) × v(a).

DIV a – деление.

Содержимое сумматора есть целая часть от деления содержимого сумматора на значение операнда а.

с(0) := .

Операции обмена с внешней памятью.

READ a – чтение. РАМ читает с входной ленты и помещает по адресу а. В качестве операнда может быть i либо *i.

WRITE a – запись. Запись значенияоперанда на выходную ленту. В операнде могут присутствовать все виды адресации.

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

Команды обращения к памяти данных.

LOAD a – занесение в сумматор. В операнде могут присутствовать все виды адресации.

Значение операнда а заносится в сумматор:

c(0) := v(a).

STORE a – запись в память из сумматора. В качестве операнда может быть i либо *i.

Значение сумматора помещается по адресу а:

v(a):= c(0).

Команды управления.

HALT – окончание вычислений. РАМ прекращает выполнение программы и останавливается.

JUMP m – безусловный переход. Счетчик команд устанавливается на команду с меткой m.

JZERO m – условный переход. Если содержимое сумматора равно 0 – счетчик команд устанавливается на команду с номером m, в противном случае значение счетчика увеличивается на единицу.

JGTZ m Если содержимое сумматора больше 0 – счетчик команд устанавливается на команду с номером  m, в противном случае значение счетчика увеличивается на единицу.

Пример 5.1. Составить РАМ-программу вычисления функции f(n)=nⁿ (будем считать, что 0⁰=0, n³0).

Блок-схема реализуемого алгоритма вычисления функции следующая.

Распределим память РАМ следующим образом:

Программа для РАМ выглядит следующим образом.