Главная » Java, Структуры данных и алгоритмы » Простейшие операции

0

После изложения разработанного высокоуровневого способа описания алгоритмов приступим к рассмотрению различных способов анализа алгоритмов.

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

1.       Записать алгоритм в виде кода одного из развитых языков программирования (например, Java).

2.       Перевести программу в последовательность машинных команд (например, байт-коды, используемые в виртуальной машине Java).

3.       Определить для каждой машинной команды / время //, необходимое для ее выполнения.

4.       Определить для каждой машинной команды / количество повторений щ команды / за время выполнения алгоритма.

5.       Определить произведение • ni ^я всех машинных команд, что и будет составлять время выполнения алгоритма.

Данный подход позволяет точно определить время выполнения алгоритма, однако очень сложен, поскольку требуется доскональное знание

машинных команд, создаваемых компилятором и средой, в которой выполняется алгоритм.

В силу этого удобнее проводить анализ непосредственно программы, написанной на языке высокого уровня, или псевдокода. Выделим ряд простейших операций высокого уровня, которые в целом не зависят от используемого языка программирования и могут использоваться в псевдокоде:

•          присваивание переменной значения,

•          вызов метода,

•          выполнение арифметической операции (например, сложение двух чисел),

•          сравнение двух чисел,

•          индексация массива,

•          переход по ссылке на объект,

•          возвращение из метода.

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

Подсчет числа простейших операций

Рассмотрим процесс подсчета числа простейших операций, выполняемых внутри алгоритма, на примере алгоритма аггауМах. Псевдокод и Java-реализация этого алгоритма представлены во фрагментах кодов 3.1 и 3.2 соответственно. Данный анализ может проводиться как на основании псевдокода, так и Java-имплементации.

•          На этапе инициализации переменной currentMax и присваивания ей значения Л[0] выполняются две простейшие операции (индексация массива и присваивание переменной значения), которые однократно выполняются в начале алгоритма. Таким образом, счетчик операций равен 2.

•          В начале выполнения цикла for счетчик / получает значение 1. Это соответствует одной простейшей операции (присваивание значения переменной).

•          Перед выполнением тела цикла проверяется условие / < п. В данном случае выполняется простейшая операция сравнения чисел. Так как первоначальное значение счетчика / равно 0, а затем его значение увеличивается на 1 в конце каждой итерации цикла, сравнение / < п проверяется п раз. Таким образом, в счетчик простейших операций добавляется еще п единиц.

•          Тело цикла for выполняется п > 1 раз (для значений счетчика 1, 2,…, п- 1). При каждой итерации A[i] сравнивается с currentMax (две простейшие операции — индексирование и сравнение), значение A[currentMax], возможно, присваивается currentMax (две простейшие операции — индексирование и присваивание значения), а счетчик i увеличивается на 1 (две простейшие операции — сложение и присваивание значения). Таким образом, при каждой итерации цикла выполняется 4 или 6 простейших операций, в зависимости от того А[/] < currentMax или А[/] > currentMax. Таким образом, при выполнении тела цикла в счетчик простейших операций добавляется 4(п – 1) или 6(п – 1) единиц.

•          При возвращений значения переменной currentMax однократно выполняется одна простейшая операция.

Итак, число простейших операций t(n), выполняемых алгоритмом аггауМах, минимально равно

2 + 1 + п + 4(п -1) + 1 =5п,

а максимально

2 + 1 +л + 6(л-1) + 1=7л-2.

Число выполняемых операций равно минимально (t(n) = 5п) в том случае, если /1[0] является максимальным элементом массива, то есть переменной currentMax не присваивается нового значения. Число выполняемых операций максимально равно (t(n) = In – 2) в том случае, если элементы массива отсортированы по возрастанию, и переменной currentMax присваивается новое значение при каждой очередной итерации цикла.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии