2015-01-30
1118
Цель работы: изучение алгоритмов поиска элемента в массиве и з акрепление навыков в проведении сравнительного анализа алгоритмов.
З а д а н и е
1. Изучить алгоритмы поиска:
1) в неупорядоченном массиве:
- линейный;
- быстрый линейный;
2) в упорядоченном массиве:
- быстрый линейный;
- бинарный;
- блочный.
2. Разработать и программно реализовать средство для проведения экспериментов по определению временных характеристик алгоритмов поиска.
3. Провести эксперименты по определению временных характеристик алгоритмов поиска. Результаты экспериментов представить в виде таблиц 12 и 13. Клетки таблицы 12 содержат максимальное количество операций сравнения при выполнении алгоритма поиска, а клетки таблицы 13 —среднее число операций сравнения.
4. Построить графики зависимости количества операций сравнения отколичества элементов в массиве.
5. Определить аналитическое выражение функции зависимости количества операций сравнения от количества элементов в массиве.
6. Определить порядок функций временной сложности алгоритмов
|
|
|
поиска.
С о д е р ж а н и е о т ч е т а
1. Тема лабораторной работы.
2. Цель работы.
3. Листинг программы.
4. Результаты работы программы.
5. Графики функций временной сложности.
6. Выводы по работе.
Таблица 12
Максимальное количество операций сравнения
| Алгоритмы поиска | Количество элементов в массиве | ||||||||
| Линейный (неупорядоченный массив) | |||||||||
| Быстрый линейный (неупорядоченный массив) | |||||||||
| Быстрый линейный (упорядоченный массив) | |||||||||
| Бинарный (упорядоченный массив) | |||||||||
| Блочный (упорядоченный массив) |
Таблица 13
Среднее количество операций сравнения
| Алгоритмы поиска | Количество элементов в массиве | ||||||||
| Линейный (неупорядоченный массив) | |||||||||
| Быстрый линейный (неупорядоченный массив) | |||||||||
| Бстрый линейный (упорядоченный массив) | |||||||||
| Бинарный (упорядоченный массив) | |||||||||
| Блочный (упорядоченный массива) |
Т е о р е т и ч е с к и е с в е д е н и я
Задача поиска заключается в том, чтобы определить наличие в массиве элемента, равного заданному.
Во многих программах поиск требует наибольших временных затрат, так что замена плохого поиска на хороший, часто ведет к существенному увеличению скорости работы программы. Выбор алгоритма поиска зависит от характера организованности массива.
|
|
|
Алгоритмы поиска в неупорядоченных массивах
