Понятия алгоритма и структуры данных

Основные сведения

Асимптотические обозначения

Свойства асимптотических функций

Введённые нами определения обладают некоторыми свойствами транзитивности, рефлексивности и симметричности.

Транзитивность:

и влечёт ;

и влечёт ;

и влечёт ;

и влечёт ;

и влечёт .

Рефлексивность:

, , .

Симметричность:

если и только если .

Обращение:

если и только если ;

если и только если .

 

Можно провести весьма условную параллель: отношения между функциями f и g подобны отношениям между числами a и b:

≈

≈

≈

≈

≈

 

 

Замечание. Следует осторожно использовать формулы при работе с О -символикой. Например, формулу ошибочно трактовать по правилу суммы

,

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

Если операция выполняется за фиксированное число шагов, не зависящее от количества данных, то принято писать O (1).

Пример 1: пусть мы смогли определить величины T (0) = 1, Т (1) = 4, Т (2) = 9 или в общем случае T (n) = (n + 1)². Требуется найти асимптотическую оценку О (f (n)), т.е. некоторую функцию вида f (n), которая бы относилась к одному из известных классов сложности алгоритмов и график которой располагался бы над графиком функции экспериментальных значений времени выполнения программы T (n), то есть описывал зависимость числа выполненных инструкций в худшем случае.

Решение: Как известно, (n + 1)² = n ² + 2 n + 1, то есть T (n) = n ² + 2 n + 1.

В качестве асимптотической оценки, т.е. функции расположенной над T (n) можно взять функцию вида f’ (n) = n ^3, так как n ^3 > n ^2 + 2 n + 1, однако тем самым мы ухудшим «мнение» эксперта об исследуемом алгоритме (он работает быстрее), так как если положить f (n) = n ^2, и найти такую константу с, чтобы выполнилось T (n) ≤ n ^2 * с. При с = 2, начиная с n0 = 3, исключая случаи запуска программы с длиной входных данных 1 и 2. Разрешая неравенство 2 n ^2 ≥ n^2 + 2 n + 1 относительно n, получаем n0 = 3.

Рис. 4 Определение константы с и n0

Заметим, что при с = 3 → n₀ = 2, что лучше чем при с = 3, так как асимптотическая оценка справедлива на большем диапазоне входных данных. Самый «идеальный» случай, когда функция f (n) превышает T (n) на всем наборе исходных данных n ≥ 1 – это условие выполняется при с = 4 и n₀ = 1.

В отличие от примера T (n) как функцию от некоторого аргумента аналитически задать сложно, а в большинстве случаев – невозможно. Единственный выход – найти верхнюю и нижнюю асимптотическую оценку характера изменения T (n). Для чего вводиться функция Ω(f (n)), которая представляет нижнюю асимптотику. Тогда надо подобрать такой вид функции роста (то есть полином f (n)) для О(f (n)) и Ω(f (n)), что они совпадут в обоих случаях с точностью до полинома – тогда получим точную асимптотическую оценку Θ(f (n))функции T (n). Согласно определению Θ(×)

.

Не трудно заметить, что условие

выполняется при с ₁ = 1 и с ₂ = 4 на всем множестве n. Поэтому для полинома точная асимптотическая оценка составляет n ².

Поскольку для f (n) = n ³ имеет строгое неравенство n ³ > n ² + 2 n + 1, то f (n) = n ³ есть o (×), то есть о(T (n)) = n ³.

 

Пример 2. По экспериментальным данным T(n) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ (n), O(n), o(n), W (n), ω (n):

n

T (n)

 

Решение. Будем решать поставленную задачу графическим методом, то есть построив график T (n), будем подбирать функции, описывающие соответствующий класс сложности алгоритмов. Построив соответствующие графики, наглядно покажем выполнения требований, согласно определениям Θ (n), O(n), o(n), W (n), ω (n).

Рис. 5 Графическое и табличное представления решения задачи.

Как видно из графиков, наилучшим приближением к экспериментальным значениям T (n) будет функция роста, описываемая полиномом вида . Действительно, согласно определению Θ(n) необходимо выполнение требования и при , и условие выполняется (на графике через c ₁ f (n) и c ₂ f (n) обозначены асимптотические границы согласно определению Θ (n) и рис. 2.). Поэтому можно утверждать, что .

Графики и таблица подтверждают, что

при и ;

при и ;

при и ;

при и .

Примеры анализа алогритмов

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

Алгоритм MaxElement (А [0.. n – 1])

// Входные данные: массив вещественных чисел А[0..n – 1]

// Выходные данные: возвращается значение наибольшего

// элемента массива А

begin

maxval <— А[0]

for i <— 1 to n - 1 do

if A[i] > maxval

then maxval <– А[i]

return maxval

end

 

Очевидно, что в этом алгоритме размер входных данных нужно оценивать по количеству элементов в массиве, т.е. числом n. Операции, выполняемые чаще всего, находятся во внутреннем цикле for алгоритма. Таких операций две: сравнение (А[i] > maxval) и присваивание (maxval <— А[i]). Какую из них считать базовой? Поскольку сравнение выполняется на каждом шаге цикла, а присваивание — нет, логично считать, что основной операцией алгоритма является операция присваивания. (Обратите внимание, что для любого массива размером n количество операций сравнения в рассматриваемом алгоритме постоянно. Поэтому не имеет смысла отдельно рассматривать эффективность алгоритма для худшего, типичного и лучшего случаев.)

Обозначим через f (n) количество выполняемых в алгоритме операций сравнения и попытаемся вывести формулу, выражающую их зависимость от размера входных данных n. Известно, что за один цикл в алгоритме выполняется одна операция сравнения. Этот процесс повторяется для каждого значения счетчика цикла i, которое изменяется от 1 до n – 1 включительно. Поэтому для f (n) получаем следующую сумму:

Значение этой суммы очень легко вычислить, поскольку в ней единица суммируется сама с собой n – 1 раз. Поэтому

.

Пример 2. Рассмотрим задачу проверки единственности элементов, то есть необходимо попарно сравнить элементы и убедиться, что все элементы массива различны.

АЛГОРИТМ UniqueElements (A [0.. n – 1])

// Входные данные: массив вещественных чисел А[0.. n– 1]

// Выходные данные: возвращается значение "true", если все

// элементы массива А различны, и "false"– в противном случае

begin

for i <– 0 to n – 2 do

for j <– i + 1 to n – 1 do if A[i] = A[j]

then return false // и досрочное завершение цикла

return true

end

 

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

По определению наихудший случай входных данных соответствует таком) массиву элементов, при обработке которого количество операций сравнений f (n) будет максимальным среди всей совокупности входных массивов раз­мером n. После анализа внутреннего цикла алгоритма приходим к выводу, что наихудший случай входных данных (т.е. когда цикл выполняется от начала до конца, а не завершается досрочно) может возникнуть при обработке массивов двух типов:

а) в которых нет одинаковых элементов;

б) в которых два одинаковых элемента находятся рядом и расположены в самом конце массива.

В подобных случаях при каждом повторе внутреннего цикла в нашем алгоритме выполняется одна операция сравнения. При этом переменная цикла j последовательно прини­мает значения от i + 1 до n – 1. Внутренний цикл каждый раз повторяется заново при каждом выполнении внешнего цикла. При этом переменная внешнего цикла i последовательно принимает значения от 0 до n – 2. Таким образом, получаем:

Обратите внимание, что этот результат можно было легко предсказать: в рас­сматриваемом алгоритме в самом худшем случае для массива, состоящего из n элементов, нужно сравнить между собой все (n– 1) n /2 различных пар элементов.

Пример 3. Для двух заданных матриц А и В размером n х n определите временную эффективность алгоритма их умножения С = АВ, основанного на опре­делении этой операции. По определению С – это матрица размером n х n, эле­менты которой являются скалярными произведениями соответствующих строки матрицы А ни столбца матрицы В, как показано ниже.

АЛГОРИТМ MatrixMultiplication (A [0..n – 1, 0.. n – 1],

В [0.. n – 1, 0.. n – 1])

// Выполняется умножение двух квадратных матриц

// размером n х n. Используется алгоритм,

// основанный на определении этой операции

// Входные данные: две квадратные n х n матрицы А к В

// Выходные данные: матрица С = АВ

BEGIN

FOR i 0 TO n-1 DO

FOR j 0 TO n-1 DO

C[i,j] 0.0

FOR k 0 TO n-1 DO

C[i,j] C[i,j]+A[i, k]*B[k,j]

RETURN C

END

 

В этом алгоритме размер входных данных соответствует размеру матрицы n. Во внутреннем цикле алгоритма выполняются две арифметические операции: умножение и сложение. В принципе, в качестве основной операции алгоритма можно выбрать как одну, так и другую операцию. Мы рассмотрим случай, когда в качестве основной выбрана операция умножения. Заметьте, что для рассматриваемого алгоритма не обязательно отдавать предпочтение одной из этих операций, поскольку на каждом шаге внутреннего цикла каждая из них выполняется только один раз. Поэтому, подсчитав, сколько раз выполняется одна из операций, мы автоматически подсчитываем и количество выполнения другой операции. А теперь давайте составим сумму для общего числа операций умножения f (n), выполняемых в алгоритме. Поскольку это число зависит только от размера исходных матриц, не требуется отдельно рассматривать наихудший, типичный и наилучший случаи.

Вполне очевидно, что на каждом шаге внутреннего цикла алгоритма выпол­няется только одна операция умножения. При этом значение переменной цикла k последовательно изменяется от нижней границы 0 до верхней границы n – 1. Поэтому количество операций умножения, выполняемых для каждой пары значений переменных i и j, можно записать следующей тройной суммой:

Для вычисления значения этой суммы воспользуемся формулами из следующего раздела:

.

Рассматриваемый алгоритм достаточно прост.

Время выполнения алгоритма на конкретном компьютере можно оценить с помощью следующего произведения:

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

где с _а ~ время выполнения одной команды сложения. Обратите внимание, что полученная оценка отличается от прежней только постоянным множителем, а не порядком роста.

Свойства логарифмов

В приведенных ниже формулах основание алгоритмов считается большей 1; его конкретная величина значения не имеет. Запись

lg a означает логарифм по основанию 10;

— логарифм по основанию ;

х и у — произвольные положительные числа.

 

Комбинаторика

1. Количество перестановок n-элементного множества:

2. Количество k -комбинаций n -элементного множества (сочетаний элементов из n):

3. Количество подмножеств n -элементного множества:

Правила работы с суммами

1.

2.

3.

4.

5.

 

Литература

1) Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.

2) Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – М.: "Вильямс", 2001. – 384 с.

3) Бентли Д. Жемчужины творчества программистов. – М.: Радио и связь, 1990.

4) Вирт Н. Алгоритмы + структуры данных = программы. – М.: Мир, 1985.

5) Вирт Н. Алгоритмы и структуры данных. – М: Мир, 1989. – 360 с.

6) Грин Д., Кнут Д. Математические методы анализа алгоритмов. – М: Мир, 1987.

7) Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. – М.: Мир, 1981.

8) Дейкстра Э. Дисциплина программирования. – М: Мир, 1978.

9) Кнут Д.Е. Искусство программирования для ЭВМ. В 3-х томах. – М.: Мир, 1976.

10) Кнут Д.Е. Искусство программирования. В 3-х томах. – М.: "Вильямс", 2000.

Основные сведения

Понятия алгоритма и структуры данных

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

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

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

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

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

3. набор допустимых операций, которые применимы к объекту описываемого типа.

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

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

Абстрактный тип данных (АТД) – это математическая модель с совокупностью операторов или операций определенных в рамках данной модели. Операции АТД реализуют функциональное назначения математической модели.

Абстрактному типу данных соответствует понятие класса в объектно-ориентированном программирование (ООП). Как известно, класс состоит свойств и методов класса. Свойства представляют собой совокупность переменных для описания объекта предметной области, а методы – набор допустимых операций над ним, реализованных в рамках данного класса.

К АТД применимы понятия инкапсуляции, абстрагирования (обобщение) и наследования парадигмы ООП:

1. Абстракция или обобщение в том смысле, что АТД можно рассматривать как обобщение понятия типа данных.

2. Наследование применимо в том смысле, что одни абстрактные типы данных могут быть описаны на основе АТД, реализация которых уже осуществлена в базовых АТД.

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

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

Независимо от содержания и сложности любые данные в памяти ЭВМ представляются последовательностью двоичных разрядов, или битов, а их значениями являются соответствующие двоичные числа. Данные, рассматриваемые в виде последовательности битов, имеют очень простую организацию или, другими словами, слабо структурированы. Для человека описывать и исследовать сколько-нибудь сложные данные в терминах последовательностей битов весьма неудобно. Более крупные и содержательные, нежели бит, «строительные блоки» для организации произвольных данных получаются на основе понятия «структуры данного».

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

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

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

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

Важный признак составной структуры данных – характер упорядоченности ее составных частей. По этому признаку структуры можно делить на линейные и нелинейные структуры.

Классификация структур данных по вышеназванным признакам приведена ниже (см. Рисунок 1).

Весьма важный признак структуры данных – ее изменчивость, то есть изменение числа элементов и/или связей между составными частями структуры. В определении изменчивости структуры не отражен факт изменения значений элементов данных, поскольку в этом случае все структуры данных имели бы свойство изменчивости. По признаку изменчивости различают структуры статические и динамические.

Рисунок 1. Классификация структур данных

 

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

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