- •Оглавление
- •Введение
- •Основные понятия и определения
- •Встроенные структуры данных(Pascal/с)
- •Варианты индивидуальных заданий на Pascal
- •Варианты индивидуальных заданий на c
- •Простые типы данных в Pascal
- •Вещественные типы
- •Вещественные типы языка Pascal
- •Сложный тип
- •Простые типы данных в с Целые типы
- •Целые типы языка c
- •Диапазоны значений целых типов языка c
- •Символьный тип
- •Перечисляемый тип
- •Вещественные типы
- •Вещественные типы языка c
- •Структурированные типы данных в Pascal Массив
- •Структура данных типа «запись»
- •Структура данных типа «множество»
- •Структурированные типы данных в c Структура данных типа «массив»
- •Структура данных типа «структура»
- •Производные структуры данных. Структура данных «строка» (Pascal/c)
- •Задание
- •Варианты индивидуальных заданий
- •Варианты задач
- •Варианты форматов
- •Назначение процедур и функций в модулях реализации сд типа строка в Pascal
- •Назначение процедур и функций в модулях реализации сд типа «строка» в c
- •Сравнительный анализ методов сортировки (Pascal/c)
- •1. Изучить временные характеристики алгоритмов.
- •6. Выводы по работе.
- •1. Выбираем элемент массива в качестве разделителя (например, первый).
- •Массив м
- •Массив м
- •Примеры программной реализации алгоритмов сортировки на языке Pascal
- •Примеры программной реализации алгоритмов сортировки на языке c
- •Сравнительный анализ алгоритмов поиска (Pascal/c)
- •Максимальное количество операций сравнения
- •Среднее количество операций сравнения
- •Алгоритмы поиска в неупорядоченных массивах Алгоритм линейного поиска
- •Алгоритм быстрого линейного поиска
- •Анализ алгоритмов линейного поиска
- •Алгоритмы поиска в упорядоченных массивах Алгоритм быстрого линейного поиска
- •Алгоритм бинарного поиска
- •Анализ алгоритма бинарного поиска
- •Алгоритм блочного поиска
- •Анализ алгоритма блочного поиска
- •Структуры данных «линейные списки» (Pascal/с)
- •Варианты индивидуальных заданий
- •Назначение процедур и функций
- •Структуры данных «стек» и «очередь» (Pascal/с)
- •Результаты работы программы
- •Варианты индивидуальных заданий
- •Варианты задач
- •Модули для реализации стека
- •Модули для реализации очереди
- •Очередь
- •Структуры данных «дерево» (Pascal/с)
- •Варианты индивидуальных заданий
- •Варианты задач
- •Назначение процедур и функций:
- •Принципы размещения бинарного дерева в памяти эвм
- •Алгоритмы обхода бинарного дерева
- •Обход бинарного дерева «в глубину» (в прямом порядке)
- •Обход бинарного дерева «в ширину» (по уровням)
- •Обход бинарного дерева в симметричном порядке
- •Обход бинарного дерева в обратном порядке
- •Алгоритмы формирования бинарного дерева
- •Рекурсивный алгоритм формирования бинарного дерева «в глубину»
- •Итеративный алгоритм формирования бинарного дерева «в глубину»
- •Алгоритм формирования бинарного дерева «в ширину»
- •Алгоритм формирования бинарного дерева «снизу вверх»
- •Рекурсивный алгоритм формирования бинарного дерева
- •Итеративный алгоритм формирования бинарного дерева
- •Алгоритм формирования бинарного дерева минимальной высоты
- •Итеративный алгоритм формирования сбалансированного бинарного дерева
- •Представление алгебраических выражений бинарными деревьями
- •Алгоритм формирования бинарного дерева по прямой польской записи
- •Алгоритм формирования бинарного дерева по обратной польской записи
- •Структуры данных «таблица» (Pascal/с)
- •Варианты индивидуальных заданий
- •Библиографический список
Анализ алгоритма бинарного поиска
Порядок функции ВС алгоритма бинарного поиска равен O(log 2 N). Это объясняется тем, что на каждом шаге поиска вдвое уменьшается область поиска. До того, как она станет равной одному элементу, произойдет не более log 2 N таких уменьшений, т.е. выполняется не более log 2 N шагов алгоритма. В лучшем случае, когда искомый элемент находится в середине массива, число сравнений не зависит от количества элементов в массиве и порядок функции ВС будет O(1).
Определим среднее число шагов при поиске элементов в массиве из N элементов. Для этого подсчитаем суммарное число шагов S при поиске каждого элемента массива. Исходя из алгоритма, не более чем N / 2 элементов ищется за log 2 N шагов, N / 4 элементов — за (log 2 N) – 1 шагов, и т.д. Отсюда.
Среднее число шагов равно S / N, что составляет O(log 2 N).
Алгоритм блочного поиска
Блочный поиск состоит в том, что массив, упорядоченный по возрастанию, разбивается на определенное число блоков. В процессе поиска искомый элемент последовательно сравнивается с последним элементом блоков. Если искомый элемент меньше последнего элемента очередного блока, то искомый элемент может находиться только внутри этого блока. Для поиска элемента в блоке можно применить линейныйпоиск.
Анализ алгоритма блочного поиска
Пусть массив состоит из N элементов и при поиске разбивается на X равных блоков. Тогда в каждом блоке будет не более N / X элементов. В худшем случае, если искомый элемент окажется в последнем блоке, то для поиска блока потребуется просмотреть X элементов массива. Выполнить линейный поиск в блоке можно, просмотрев не более чем N / X элементов. Следовательно, общее число обрабатываемых элементов не превышает X + N / X. Эта величина зависит от числа блоков и будет минимальна, когда ее производная равна нулю, т.е. при. Число записей в блоке так же равно. При таком разбиении массива на блоки в худшем случае понадобиться обработать не более чемэлементов массива, а в среднем —элементов.
К о н т р о ль н ы е в о п р о с ы
1. В чем заключается задача поиска?
2. Всегда ли быстрый линейный поиск быстрее линейного поиска?
3. От чего зависит время поиска в неупорядоченном массиве?
4. Чем алгоритм быстрого линейного поиска в упорядоченном массиве отличается от алгоритма быстрого линейного поиска в неупорядоченном массиве?
5. В чем заключается бинарный поиск?
6. Определите индексы элементов массива, бинарный поиск которых наиболее продолжителен.
7. Разработайте и реализуйте итеративный и рекурсивный алгоритмы бинарного поиска?
8. В чем заключается блочный поиск?
9. От чего зависит время блочного поиска?
10. Как правильно выбрать количество блоков в блочном поиске?
11. Определите максимальное количество элементов массива, которые могут быть обработаны при блочном поиске.
12. Пусть искомый элемент равен i-му элементу массива. Какой алгоритм рациональнее использовать в этом случае?
13. Выполните сравнительный анализ алгоритмов поиска для случая, когда искомого элемента нет в массиве.
14. Выполните сравнительный анализ алгоритмов поиска для случая, когда в массиве только один элемент.
15. Реализуйте алгоритмы поиска на языке программирования высокого уровня. Выполните трассировку при поиске в массиве из одного элемента.
16. От чего завист порядок функции временной сложности алгоритмов поиска. Каким он может быть для различных алгоритмов?
Л а б о р а т о р н а я р а б о т а № 5