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

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

2.2. Простейшие операции

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

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

• 1. Записать алгоритм в виде кода одного из развитых языков программирования (например, Java).
  2. Перевести программу в последовательность машинных команд (например, байт-коды, используемые в виртуальной машине Java).
  3. Определить для каждой машинной команды i время t_i, необходимое для ее выполнения.
  4. Определить для каждой машинной команды i количество повторений команды n_i за время выполнения алгоритма.
  5. Определить произведение t_i*n_i всех машинных команд, что и будет составлять время выполнения алгоритма.

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

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

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

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

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

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

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

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

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

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

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

3.1 и 3.2 соответственно. Данный анализ может проводиться как на ос-новании псевдокода, так и Java-реализации.

• • На этапе инициализации переменной currentMax и присваивания ей значения A[0] выполняются две простейшие операции (индексация массива и присваивание переменной значения), которые однократно выполняются в начале алгоритма. Таким образом, счетчик операций равен 2.
  • В начале выполнения цикла for счетчик i получает значение 1. Это соответствует одной простейшей операции (присваивание значения переменной).
  • Перед выполнением тела цикла проверяется условие i<n. В данном случае выполняется простейшая операция сравнения чисел. Так как первоначальное значение счетчика i равно 0, а затем его значение увеличивается на 1 в конце каждой итерации цикла, сравнение i<n проверяется n раз. Таким образом, в счетчик простейших операций добавляется еще n единиц.
  • Тело цикла for выполняется n ≥ 1 раз (для значений счетчика 1, 2,..., n- 1). При каждой итерации A[i] сравнивается с currentMax (две простейшие операции – индексирование и сравнение), значение A[i], возможно, присваивается currentMax (две простейшие операции – индексирование и присваивание значения), а счетчик i увеличивается на 1 (две простейшие операции – сложение и присваивание значения). Таким

образом, при каждой итерации цикла выполняется 4 или 6 простейших операций, в зависимости от того A[i] ≤ currentMax или A[i] > currentMax. Таким образом, при выполнении тела цикла в счетчик простейших операций добавляется

4(n - 1) или 6(n - 1) единиц.

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

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

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

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

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

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

2.3. Анализ средних и худших показателей

На примере метода аггауМах можно убедиться, что при определенном типе исходных данных алгоритм выполняется быстрее, чем при других. В данном случае можно попытаться выразить время выполнения алгоритма как среднее, взятое на основе результатов, полученных при всех возможных исходных данных. К сожалению, проведение анализа с точки зрения средних показателей является весьма проблематичным, так как в этом случае требуется определить вероятностное распре-деление входящего потока. На рис. 3.3 схематично представлена зависимость времени выполнения алгоритма от распределения входного потока данных. Например, если исходные данные только типа «А» или «D».

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

• связи с этим в дальнейшем будем по умолчанию указывать худший показатель времени выполнения алгоритма (если не будет оговоре-но другое условие). Можно сказать, что в худшем случае алгоритм arrayMax выполняет t(n) = 7n - 2 простейших операций, то есть максимальное число простейших операций, выполняемых алгоритмом при использовании всех исходных данных размера n, составляет 7n - 2.

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

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

Рис. 1.2. Различие между наилучшим и наихудшим показателями времени выполнения алгоритма

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

2.4. Асимптотическая нотация

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

• Действительно ли необходим такой уровень детализации?
• Действительно ли так важно установить точное число простейших операций, выполняемых алгоритмом?
• Насколько досконально следует определять количество простейших операций? Например, сколько простейших операций выполняется в команде у = a*x + b? (Можно определить, что выполняются две арифметические операции и одна операция присваивания, но , с другой стороны, в этом случае не учитывается еще одна «скрытая» операция присваивания результата произведения a*x временной переменной перед выполнением операции сложения.)
  • целом каждый этап псевдокода или команда программы на языке программирования содержит небольшое число простейших операций, которое не зависит от размера исходных данных. Таким образом, можно проводить упрощенный анализ, при котором число простейших операций определяется применением некоторой константы, путем подсчета выполненных шагов псевдокода или команд программы. Возвращаясь к алгоритму arrayMax, упрощенный анализ даст следующий результат: алгоритм выполняет от 5n до 7n - 2 шагов при размере исходных данных n.

При анализе алгоритмов следует рассматривать увеличение времени его выполнения как функцию исходных данных n, уделяя основное внимание глобальным аспектам и не вдаваясь в отдельные мелкие детали. Зачастую достаточно просто знать, что время выполнения алгоритма, например, arrayMax, увеличивается пропорционально n. Это означает, что действительное время выполнения алгоритма является произведением n на некий постоянный множитель, который определяется условиями аппаратного и программного обеспечения, и может колебаться в определенных пределах в зависимости от особенностей исходных данных.

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

Рассмотрим основные понятия так называемой нотация большого

• [6].

Пусть f(n) и g(n) являются функциями, которые преобразуют неотрицательные целые числа в действительные. Докажем, что f(n) есть O(g(n)), если существует действительная константа с > 0 и целочисленная константа n₀ > 1, такие, что f(n) < cg (n) для любого целого числа n

• n₀. Такое определение функции зачастую называется нотацией большого О, так как иногда говорят, что f(n) является большим O функции g(n). Другими словами, можно сказать, что f(n) есть порядковая функция g(n) (определение показано на рис. 3.4).

Пример: 7n - 2 есть O(n).

Доказательство: по определению нотации большого О необходимо найти действительную константу с > 0, а также целочисленную константу n₀ ≥1, так, что 7n-2n₀ ≤ сn для любого целого числа, n≥n₀. Одним из очевидных вариантов является с = 7, а n₀ = 1. Безусловно, это один из бесконечного множества вариантов; с в данном случае может принимать значение любого действительного числа, равного или большего 7, а n₀ - любое целочисленное значение, большее или равное 1.

Нотация большого О позволяет выразить, что функция n «меньше или равна» другой функции (в определении это выражается знаком «≤ ») до определенного постоянного значения (константа с в определении) и по мере того, как n стремится к бесконечности (условие «n ≥ n₀» в определении).