Введение 4
Постановка задачи 5
Обзор литературы 6
Глава 1. Обзор существующих решений 9
Глава 2. Исследование трудоемкости 10
2.1. Общие положения исследования 10
2.2. Построение гистограммы частот 11
2.2.1 Формула Стерджесса 12
2.2.2 Эмпирический метод 13
2.2.3 Принцип наихудших измерений 13
2.3. Определение объема выборки 13
2.3.1 Метод с использованием схемы Бернулли 14
2.3.2 Метод на основе закона распределения 14
2.4. Используемые законы распределения 15
2.4.1 Равномерное распределение 16
2.4.2 Треугольное распределение (распределение Симпсона) 17
2.4.3 Бета-распределение 17
2.5. Восстановление параметров функции плотности 18
2.6. Рассмотрение гипотезы о законе распределения 19
2.6.1 Критерий согласия Пирсона (у2) 19
2.6.2 Критерий согласия Колмогорова 20
2.7. Прогнозирование функции трудоемкости 21
2.7.1 Коэффициент детерминации (Я2) 22
Глава 3. Проведение экспериментального исследования трудоемкости 23
3.1. Описание выбранного алгоритма 23
3.2. Этап предварительного исследования 24
3.2.1 Основные шаги 24
3.2.2 Результаты предварительного исследования 27
3.3. Этап основного исследования 30
3.3.1 Основные шаги 30
3.3.2 Результаты основного исследования 32
Глава 4. Создание инструментария 36
4.1. Постановка задачи 36
4.2. Архитектура системы 36
4.3. Описание реализации 37
Выводы 40
Заключение 41
Список литературы 42
Оценка эффективности алгоритмов является важным этапом в создании качественных программных средств, причем один из критериев качества — временная эффективность, особенно актуальная для систем, работающих в режиме реального времени. Очевидно, что временная эффективность компьютерной программы связана с функцией трудоемкости алгоритма, т. е. с точным количеством операций, задаваемых алгоритмом в основе программной реализации. Однако, асимптотические оценки вычислительной сложности, получаемые в теоретическом исследовании алгоритмов, не всегда справедливы для конечного диапазона длин входов, что объясняется большими значениями коэффициентов у компонентов функции трудоемкости. В работе предлагается практический подход на основе эмпирического анализа времени выполнения программной реализации, для чего создана автоматизированная система с критерием оценки по величине доверительной трудоемкости в выбранном диапазоне входных данных.
Вычисление доверительной трудоемкости основано на построении доверительных интервалов оцениваемой величины трудоемкости с заданной доверительной вероятностью в классическом подходе математической статистики [1]. Данный метод требует использования репрезентативных выборок достаточно большого объема и многократного запуска программных реализаций исследуемых алгоритмов в соответствующем многоэтапном процессе; поэтому, несомненно, актуальной является разработка системы для автоматизированного проведения анализа, значительно сокращающего время оценки качества алгоритмов.
В данной работе рассматривается построение такой системы и исследование применимости предложенного подхода на основе доверительной трудоемкости для большего количества алгоритмов.
Исследованы различные дополнительные методы для применения методологии [1] на более широкий класс алгоритмов.
Разработана автоматизированная система для оценки качества алгоритмов по доверительной трудоемкости, вычисленной в процессе эмпирического анализа программной реализации. Преимущество системы состоит в получении гарантирующей оценки на основе статистических заключений с заданным уровнем значимости. Исходный код и документация системы находятся в публичном репозитории в GitHub [39].
