Курсовая работа: Анализ алгоритмов нечисленной обработки данных

Рисунок 1. График результатов линейного поиска

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

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

5.2 Двоичный поиск

Анализ двоичного поиска был проведен на примере числового одномерного массива длиной в 16, 128, 512, 1024 элементов. В качестве искомых элементов были взяты числа, расположенные в первой, средней, последней и произвольной позициях. Для двоичного поиска теоретическое время поиска определяется по формуле Tтеор.=[время сравнения]× log2N

Результаты приведены в таблице, которая приведена ниже.

Таблица 3. Результаты двоичного поиска

Количество элементов массива	16		128		512		1024
Позиция элемента	Искомый элемент	Количество сравнений	Искомый элемент	Количество сравнений	Искомый элемент	Количество сравнений	Искомый элемент	Количество сравнений
Первая	0	4	0	7	0	9	0	10
Средняя	13	1	310	1	156	1	491	1
Последняя	45	4	901	7	491	9	942	10
Произвольная	2	2	80	3	127	7	660	9
Элемент отсутствует	88	4	1001	7	1002	9	1003	10
Среднее количество сравнений	3		5		7		8
Теоретическое значение	4		7		9		10

Ниже приведен график зависимости времени поиска от количества элементов массива.

Рисунок 2. График результатов двоичного поиска

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

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

5.3 Анализ сортировки деревом

Анализ сортировки деревом был проведен на примере массива длиной в 16, 128, 512, 1024 элементов.

Результаты представлены в виде нижеследующей таблицы.

Таблица 6. Результаты сортировки

Количество элементов в массиве	16	128	512	1024
Количество перестановок	18	130	514	1026

Ниже приведен график сортировки деревом.

Рисунок 3. График сортировки деревом.

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

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

Заключение

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

Список литературы

1. Лорин Г. Сортировка и системы сортировки. М.: Наука, 1983г.

2. Лавров С.С, Гончаров Л.И. Автоматическая обработка данных. Хранение информации в памяти ЭВМ. М.: Наука, 1971г.

3. Попов В.Б. Turbo Pascal. М.: Финансы и статистика, 2007г.

Приложение А

Таблицы идентификаторов