Анализ алгоритмов нечисленной обработки данных (стр. 3 из 4)
Данная процедура выводит на экран сформированный массив, используя те же входные параметры, что и процедура VVod.
Предназначена для записи во внешний текстовый файл сортируемый массив после заданного числа перестановок. Входные параметры: текстовый файл F(по ссылке), n – длина массива, a – записываемый сортируемый массив, m – количество перестановок.
Эта процедура предназначена для поиска заданного элемента методом линейного поиска. Входные параметры: n – длина массива, a – исходный массив, x – заданный элемент. Локальные переменные: i – индекс элемента, счетчик, k – количество сравнений.
Данная процедура реализует двоичный поиск. Входные параметры – те же, что и в процедуре Lin_Poisk. Локальные переменные: k – количество сравнений, ni – индекс нижней границы массива, vi – индекс верхней границы массива, sri – индекс среднего элемента массива.
4.2.6 Процедура Tree
Для построения дерева из исходного массива используется процедура Tree. Она формирует дерево b из массива a. Входные параметры: a - исходный массив (по значению), n – длина массива (по значению). Выходной параметр: b – двумерный массив (дерево). Локальные переменные: i,j – индексы элемента в дереве.
Сортирует дерево, полученное из исходного массива. Входные параметры: b – исходное дерево (по значению), n – длина массива (по значению). Выходной параметр: b1 – результирующий массив (отсортированное дерево). Локальные переменные: k – количество узлов в дереве, m – количество перестановок, i1 – индекс элемента в дереве (массиве).
4.3 Область и условия применения программы
В данной программе были разработаны алгоритмы нечисленной обработки данных – линейный и двоичный поиск, сортировка деревом. Сортировку деревом очень удобно использовать, когда необходимо сэкономить максимально возможно количество времени, но для представления дерева требуются большие затраты дополнительной памяти.
Программа является познавательной, её целесообразно использовать в качестве обучающего примера.
На основе проведенных тестов программы был проведен анализ алгоритмов нечисленной обработки данных на примере массива длиной в 16, 128, 512, 1024 элементов.
Для проведения анализа линейного поиска в качестве заданного элемента были взяты числа, расположенные в начале, в середине, в конце и в произвольной позиции массива. Для линейного поиска теоретическое время поиска определяется по формуле Tтеор.=[время сравнения]×N/2
Результаты приведены в нижеследующей таблице.
Таблица 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 видно, что график линейного поиска имеет линейный характер. Теоретическое время незначительно отличается от практического, что означает правильность результатов выполнения линейного поиска.
Данный метод удобен для массивов с малой длиной, но использование его для больших массивов занимает много времени.
Анализ двоичного поиска был проведен на примере числового одномерного массива длиной в 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 видно, что график двоичного поиска имеет логарифмический характер. Теоретическое время незначительно отличается от практического, что означает правильность результатов выполнения двоичного поиска.
Данный метод удобен для массивов с большой длиной, но его использование возможно только в упорядоченных массивах.
Анализ сортировки деревом был проведен на примере массива длиной в 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