Порядок выполнения лабораторной работы

Работа предполагает выполнение следующих этапов.

1. Знакомство со всеми разделами руководства.

2. Получение у преподавателя задания на асимптотическую и верхнюю оценку сложности алгоритма (см. прил. 1) и выполнение этой оценки.

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

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

5. Построить график зависимости времени выполнения от объема входных данных.

Содержание отчета о выполненной работе

Отчет о выполненной работе должен содержать.

1. Название и цель работы.

2. Формулы асимптотической и верхней оценки сложности заданного алгоритма.

3. Исходный код программы экспериментальной оценки временной сложности заданного алгоритма для массива большой размерности.

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

5. График зависимости времени выполнения алгоритма от объема исходных данных.

Контрольные вопросы

1. Чем характеризуется сложность алгоритма?

2. Как оценивается асимптотическая сложность алгоритма?

3. Как получается верхняя оценка сложности алгоритма?

4. Отличаются ли и на сколько асимптотическая и верхняя оценка сложности алгоритма?

5. Какие функции используются для представления верхней оценки сложности алгоритма?

6. У каких известных вам алгоритмов сложность является константной, а у каких - линейной?

7. Как оценивается сложность экспериментальным методом?

8. Совпадают ли результаты экспериментальной и верхней оценок и, если нет, то на сколько они отличаются?

9. Как влияет размер массива на временную сложность алгоритма?

10. Как влияет количество циклов повторения исследуемого алгоритма на погрешность определения времени его выполнения?

11. Как определяется емкостная сложность алгоритма?

12. Как связаны временная и емкостная сложность алгоритма?

Лабораторная работа №2 исследование и оценка алгоритмов поиска Краткая теория

Цель работы. Разработка программ, реализующих различные алгоритмы поиска, и оценка их временной и пространственной сложности.

Поиск. Основные определения и классы алгоритмов

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

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

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

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

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

1. совпадению,

2. близости снизу

3. близости сверху.

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

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

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

Общий алгоритм поиска по совпадению ключа можно представить так.

1. Ввести исходный массив (ключей).

2. Повторять

ввести аргумент поиска и вывести результат

пока не надоест.

3. Закончить.

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

Наиболее распространенными являются три алгоритма поиска:

1. Линейный;

2. Дихотомический:

3. Интерполирующий.