46775 (Анализ алгоритмов нечисленной обработки данных), страница 2
Описание файла
Документ из архива "Анализ алгоритмов нечисленной обработки данных", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "46775"
Текст 2 страницы из документа "46775"
Результаты приведены в нижеследующей таблице.
Таблица 2. Результаты линейного поиска
| Количество элементов массива | 16 | 128 | 512 | 1024 | |||||
| Позиция элемента | Искомый элемент | Количество сравнений | Искомый элемент | Количество сравнений | Искомый элемент | Количество сравнений | Искомый элемент | Количество сравнений | |
| Первая | 5 | 1 | 0 | 1 | 48 | 1 | 0 | 1 | |
| Средняя | 15 | 8 | 85 | 64 | 894 | 256 | 465 | 512 | |
| Последняя | 3 | 16 | 314 | 128 | 191 | 512 | 242 | 1024 | |
| Произвольная | 4 | 13 | 272 | 5 | 747 | 511 | 425 | 10 | |
| Элемент отсутствует | 101 | 16 | 999 | 128 | 982 | 512 | 987 | 1024 | |
| Среднее значение | 10,8 | 65,2 | 358,4 | 513,6 | |||||
| Теоретическое значение | 8 | 64 | 256 | 512 | |||||
По данным таблицы 2 построены графики функции зависимости времени поиска от количества элементов массива (рисунок 2).
Рисунок 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г.
Приложение А
Таблицы идентификаторов
Таблица А.1: Идентификаторы основной программы
| Имя параметра | Физический смысл параметра | Тип параметра |
| n | Длина исходного массива до 1024 элементов | integer |
| i | Счетчик, индекс элемента массива | integer |
| j | Счетчик, индекс элемента массива, указатель | integer |
| x | Искомое число | integer |
| a | Одномерный числовой массив (исходный массив) | mas=array [1..1024] of integer |
| b | Двумерный числовой массив, дерево, образованное из исходного массива | mas2=array [1..1024, 1..5] of integer |
| b1 | Двумерный числовой массив, сортируемое дерево | mas2=array [1..1024, 1..5] of integer |
| F | Текстовый файл для хранения исходного массива | text |
| F_1 | Текстовый файл для хранения отсортированного массива, сортируемого массива после каждой перестановки | text |
Таблица А.2: Идентификаторы процедуры VVod
| Имя параметра | Физический смысл параметра | Тип параметра |
| i | Счетчик, индекс элемента формируемого массива | integer |
| n | Длина формируемого массива | integer |
| a | Формируемый массив | mas=array [1..1024] of integer |
Таблица А.3: Идентификаторы процедуры Vivod
| Имя параметра | Физический смысл параметра | Тип параметра |
| i | Счетчик, индекс элемента выводимого на экран массива | integer |
| n | Длин массива, выводимого на экран | integer |
| a | Выводимый на экран массив | mas=array [1..1024] of integer |
Таблица А.4: Идентификаторы процедуры Save_To_File
| Имя параметра | Физический смысл параметра | Тип параметра |
| i1 | Счетчик, индекс элемента массива, сохраняемого в файл | integer |
| F | Файл, в который необходимо записывать сортируемый массив после каждой перестановки | text |
| n | Длина массива | integer |
| a | Исходный массив, сохраняемый в файл | mas=array [1..1024] of integer |
| m | Количество перестановок | integer |
А.5 Идентификаторы процедуры Lin_Poisk
| Имя параметра | Физический смысл параметра | Тип параметра |
| i | Счетчик, индекс элемента массива | integer |
| k | Количество сравнений | integer |
| n | Длина массива | integer |
| a | Массив, в котором необходимо найти искомый элемент | mas=array [1..1024] of integer |
| x | Искомый элемент | integer |
