Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования.pdf

Таблица 1

По своей структуре различают следующие типы алгоритмов: линейные, разветвляющиеся и циклические. В линейных схемах алгоритмов все предписания выполняются одно за другим. Например, алгоритм вычисления длины окружности по известной площади круга (рис.1). В разветвляющихся схемах алгоритмов для конкретных исходных данных выполняются не все заданные предписания. Однако какие именно предписания будут выполняться, конкретно определяется в процессе выполнения алгоритма в результате проверки некоторых условий. Разветвляющийся алгоритм всегда избыточен. Примером разветвляющегося алгоритма является алгоритм, приведенный на рис.2 и определяющий, пройдет ли график функции y=3x+4 через точку с координатами x1,y1.

Рис. 3

Рис. 2

Рис. 1

Циклическим алгоритмом называется такой алгоритм, в котором можно выделить многократно повторяющуюся последовательность предписаний, называемую циклом. Для таких алгоритмов характерно наличие параметра цикла, которое перед входом в цикл имеет начальное значение, а затем изменяется внутри цикла. Имеется также предписание о проверке условия окончания цикла. Применение циклов сокращает текст алгоритма и, в конечном итоге, длину программы. Примером циклического алгоритма может служить алгоритм, приведенный на рис.3 и определяющий факториал натурального числа n. В этом алгоритме введена дополнительная переменная i, которая является параметром цикла и изменяется от начального значения 1 до конечного значения n c шагом 1. На каждом шаге итерации искомая величина f умножается на переменную цикла. В реальных задачах, как правило, сочетаются все три типа алгоритмов. Способ описания алгоритма с помощью алгоритмического языка подробно рассматривается в следующем разделе.

1.3 Анализ алгоритмов

Время выполнения алгоритма или операции над структурой данных зависит, как правило, от целого ряда факторов, вследствие чего возникает вопрос – как следует проводить его измерение. При реализации алгоритма можно определить затраты времени, регистрируя действительное время, затраченное на выполнение алгоритма в каждом отдельном случае запуска с различными исходными данными [8]. Подобные измерения должны проводиться с достаточной точностью с помощью системных вызовов, встроенных в язык или операционную систему, для которой написан данный алгоритм (например, метод System.currentTimeMillis() в Java или вызовом исполняющей среды с возможностью профилирования). В общем, требуется определить, каким образом время выполнения программы зависит от количества исходных данных. Для решения этой задачи можно провести ряд экспериментов, в которых будет использовано различное количество исходных данных . Далее полученные результаты наглядно представляются с помощью графика, где каждый случай выполнения алгоритма обозначается с помощью точки, координата х которой равна размеру исходных данных n, а координата у – времени выполнения алгоритма t ( рис. 1.1). Чтобы сделать определенные выводы на основе полученных экспериментов, необходимо использовать качественные образцы исходных данных и провести достаточно большое число экспериментов, что позволит определить некоторые статистические характеристики в отношении времени выполнения алгоритма.

Рис.1.1

Результаты экспериментального исследования времени выполнения алгоритма. Точка с координатами (n, t) обозначает, что при размере

исходных данных n время выполнения алгоритма составило t миллисекунд (мс).

На рис. 1.1, а представлены результаты выполнения алгоритма на компьютере с быстрым процессором, на рис. 1.1, b представлены результаты выполнения алгоритма на компьютере с медленным процессором. В целом можно сказать, что время выполнения алгоритма или ме-тода доступа к полям структуры данных возрастает по мере увеличения размера исходных данных, хотя оно зависит и от типа данных, даже при равном размере. Кроме того, время выполнения зависит от аппаратного обеспечения ( процессора, тактовой частоты, размера памяти, места на диске и др .) и программ программного обеспечения (операционной среды, языка программирования, компилятора, интерпретатора и др.), с помощью которых осуществляется реализация, компиляция и выполнение алгоритма. Например, при всех прочих равных условиях время выполнения алгоритма определенного количества исходных данных будет меньше при использовании более мощного компьютера или при записи алгоритма в виде программы на машинном коде по сравнению с его исполнением виртуальной машиной, проводящей интерпретацию в байт-коды.

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

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

Обычно для сравнительного анализа рассматривается, так называемая общая методология анализа времени выполнения алгоритмов, кото-рая:

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

Сущность такой методологии состоит в том, что каждому алгоритму соответствует функция, которая представляет время выполнения алгоритма как функцию размера исходных данных n. Наиболее распространенными являются функции n и n². Например, можно записать следующее утверждение: «Время выполнения алгоритма А пропорционально n». В этом случае, в результате проведения экспериментов, окажется, что время выполнения алгоритма А при любом размере входных данных n не превышает значения cn, где с является константой, определяемой условиями используемого аппаратного и программного обеспечения. Если имеются два алгоритма А и В, причем время выполнения алгоритма А пропорционально n, а время выполнения В пропорционально n², то предпочтительнее использовать алгоритм А, так как функция n возрастает медленнее, чем функция n ². Выводы о скорости возрастания этих функций являются, безусловно, очевидными, однако предлагаемая методология содержит точные определения данных понятий. Прежде чем перейти к описанию общей методики, определим понятие псевдокод и области его применения.

Глава 2. Анализ алгоритмов

2.1. Псевдокод

Зачастую программистам требуется создать описание алгоритма, предназначаемое только для человека. Подобные описания не являются программами, но вместе с тем они более структурированы, чем обычный текст. В частности, «высокоуровневые» описания сочетают естественный язык и распространенные структуры языка программирования, что делает их доступными и вместе с тем информативными. Такие описания способствуют проведению высокоуровневого анализа структуры данных или алгоритма. Подобные описания принято называть псевдокодом.

Проблема «максимума в массиве» является простой задачей поиска элемента с максимальным значением в массиве А, содержащем n целых чисел. Для решения этой задачи можно использовать алгоритм аггауМах, который осуществляет просмотр массива А с использованием цикла for.

Псевдокод алгоритма аггауМах представлен во фрагменте кода, а полная реализация программы Java представлена в следующем фрагменте кода.

Input: массив А, содержащий п целых чисел (n > 1).

Output: элемент с максимальным значением в массиве A.

1 currentMax ←А [0] выполняется один раз

2 for i ←1 to n - 1 do выполняется от 1 до n, n-1 раз соответственно

1. if currentMax < A[i] then выполняется n-1 раз
2. currentMax ← А [i] выполняется максимально n-1 раз
3. return currentMax выполняется один раз

Фрагмент кода Алгоритм аггауМах

• Тестируем программу алгоритма поиска максимального элемента массива.

public class ArrayMaxProgram {

• находит элемент с максимальным значением в массиве А, содержащем n целых //чисел.

static int arrayMax(int[ ] A, int n) {

int currentMax = A[0]; // выполняется один раз

for (int i = l; i < N; i++) /* выполняется от 1 до n, n-1 раз соответ-ственно. */

if (currentMax < A[i]) // выполняется n-1 раз currentMax = A[i]; // выполняется максимально n-1 раз return currentMax; // выполняется один раз

}

• Тестирующий метод, вызываемый после выполнения программы. public static void main(String args[ ]) {

int[ ] num = { 10, 15, 3, 5, 56, 107, 22, 16, 85 }; int n = num.length; System.out.print("Array:");

for (int j = 0; i < n; i++) System.out.print("" + num[i]); System.out.println(".");

System.out.println("The maximum elementis" + arrayMax(num,n) +

".");

}

}

Фрагмент кода Алгоритм arrayMax внутри законченной Java-программы.

Как можно заметить, псевдокод выглядит компактнее Java-кода, и его легче читать и понимать. При анализе псевдокода можно поспорить

• правильности алгоритма arrayMax c простым аргументом. Переменная currentMax первоначально принимает значение первого элемента массива А. Можно утверждать, что перед началом итерации по номеру i значение currentMax равно максимальному значению среди первых i элементов массива А. Так как при повторении I значение currentMax сравнивается с A[i], то, если это утверждение верно перед данной итерацией, оно будет верно и после нее для i + 1 (которое является следующим значением счетчика i).Таким образом, после количества итераций n - 1 значение currentMax будет равно элементу массива А, содержащему максимальное значение.

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

• • Выражения. Для написания числовых и логических выражений используются стандартные математические символы. Знак стрелки применяется в качестве оператора присваивания в командах присваивания (равнозначен оператору «=» языка Java). Знак «=» используется для передачи отношения равенства в логических выражениях (что соответствует оператору «= =» языка Java).
  • Объявление метода. Имя алгоритма (paraml, param2,...) объявляет «имя» нового метода и его параметры.
  • Структуры принятия решений. Условие if, then – действия, если условие верно [else – если условие не верно]. Отступы используются для обозначения выполняемых в том или другом случае действий.
  • Цикл while, while – условие, do - действия. Отступ обозначает действия, выполняемые внутри цикла.
  • Цикл repeat, repeat – действия, которые выполняются, пока выполняется условие until. Отступ обозначает действия, выполняемые внутри цикла.
  • Цикл for. for – описание переменной и инкремента, do – действия. Отступ обозначает действия, выполняемые внутри цикла
  • Индексирование массива. A[i] обозначает i-ую ячейку массива А. Ячейки массива А с количеством ячеек n индексируются от A[0] до A[n
• 1] (как в Java).
  • Обращения к методам, object.method (args) (часть object необязательна, если она очевидна).
  • Возвращаемое методом значение. Значение return. Данный оператор возвращает значение, указанное в методе, вызывающим данный метод.