Навигация
5 Анализ результата
На основе проведенных тестов программы был проведен анализ алгоритмов нечисленной обработки данных на примере массива длиной в 16, 128, 512, 1024 элементов.
5.1 Линейный поиск
Для проведения анализа линейного поиска в качестве заданного элемента были взяты числа, расположенные в начале, в середине, в конце и в произвольной позиции массива. Для линейного поиска теоретическое время поиска определяется по формуле 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 видно, что график линейного поиска имеет линейный характер. Теоретическое время незначительно отличается от практического, что означает правильность результатов выполнения линейного поиска.
Данный метод удобен для массивов с малой длиной, но использование его для больших массивов занимает много времени.
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 видно, что график двоичного поиска имеет логарифмический характер. Теоретическое время незначительно отличается от практического, что означает правильность результатов выполнения двоичного поиска.
Данный метод удобен для массивов с большой длиной, но его использование возможно только в упорядоченных массивах.
Похожие работы
... процессов и явлений, использовать графику машины для повышения наглядности изучаемого материала. Использование пакетов прикладных учебных программ, готового программного обеспечения является одной из самых важных компонентов формирования компьютерной грамотности. При этом значительно расширяются межпредметные связи между многими учебными дисциплинами, особенно между математикой и информатикой. ...
... практичных алгоритмов оптимизированного перебора, позволяющих за разумное время осуществлять распараллеливание достаточно больших участков. Анализ работ, посвященных оптимизации кода для процессоров с параллелизмом на уровне команд показывает, что для достижения наилучших результатов необходимо применение комплекса оптимизаций, среди которых можно выделить следующие классы. Преобразования циклов ...
... і слова в орфографічному словнику контроль орфографічної правильності його написання слід здійснювати за правилами орфографії. Зараз готують до затвердження наступний п’ятий правопис. Тому в процесі редагування треба враховувати динамічність правопису і слідкувати за правописними змінами. Відхилення від правильного написання допустиме лише тоді, коли в повідомленні йдеться про юридичну справу і ...
... дисциплин. Горн рассматривает эти вопросы, отталкиваясь в своих рассуждениях от профессиональных интересов ученых в этой области еще на, стадии получения ими образования: «Информационно-компьютерная наука рассматривает прагматические аспекты использования символов их пользователями и интерпретаторами в качестве еще одного центрального вопроса таким же образом, как эти аспекты должны исследоваться ...
0 комментариев