Введение 3
Постановка задачи 4
Обзор литературы 5
Глава 1. Методика исследования 7
1.1. Функция трудоемкости алгоритма 7
1.2. Трудоемкость ─ дискретная ограниченная случайная величина 7
1.3. Аппроксимация гистограммы относительных частот трудоемкости бета-распределением 8
1.4. Понятие доверительной трудоемкости 9
1.5. Методика исследования на доверительную трудоемкость 9
Глава 2. Алгоритм триангуляции 11
2.1. Триангуляция Делоне 11
2.2. Входные данные, единицы измерения 12
2.3. Генерация входных данных 13
Глава 3. Эмпирический анализ алгоритма пузырьковой сортировки 14
3.1. Расчёт объёма выборки 14
3.2. Предварительный этап 14
3.3. Основной этап 15
Глава 4. Эмпирический анализ алгоритма триангуляции 18
4.1. Расчёт объёма выборки 18
4.2. Предварительный этап 19
4.3. Основной этап 20
Заключение 22
Список литературы 23
Актуальность темы исследования обусловлена тем, что существует огромное количество различных компьютерных алгоритмов, в том числе и для решения одной и той же задачи, для которой необходимо проводить анализ их эффективности с последующим выбором наиболее подходящего алгоритма в той или иной области применения. На вход алгоритм может принимать раз-личные наборы данных и разные реализации могут хорошо и быстро работать с одними наборами, но очень плохо с другими. Проведение оценки эффективности позволяет определить, что именно будет работать лучше в конкретных условиях.
Целью работы является построение доверительных интервалов оцениваемой величины трудоемкости компьютерного алгоритма с заданной доверительной вероятностью.
Таким образом, в работе проведен эмпирический анализ алгоритма триангуляции Делоне, разработанного по методу “Разделяй и властвуй” с программной реализацией в библиотеке Triangle.NET [6], которая является портом программного обеспечения Triangle[7]. При этом эмпирический анализ проводился по методике, нацеленной на получение доверительной трудоемкости, которая позволяет значительно сузить оцениваемый сегмент варьирования трудоемкости. В качестве иллюстративного примера рассмотрено также применение данной методики к алгоритму пузырьковой сортировки.
В процессе выполнения предварительного этапа исследования с проверкой гипотезы о законе распределения значений трудоемкости алгоритма как дискретной ограниченной случайной величины была построена гистограмма относительных частот, которые наблюдаются в вычислительном эксперименте, и визуально оценен характер распределения. Гипотеза о возможности аппроксимации бета-распределением подтвердилась.
После выполнения основного этапа получено значительное отличие трудоёмкости в худшем случае и доверительной трудоёмкости, которая с коэффициентом доверия 95% не будет превышена.
