Реферат
Введение 3
1 Анализ задания 4
1.1 Выбор анализатора 4
1.2 Обзор готовых решений 5
1.2.1 Google benchmark 5
1.2.2 BigO Calculator 5
1.2.3 Сравнение готовых решений 6
1.3 Требования к динамическому анализатору 8
1.4 Выводы по главе 8
2 Этапы проектирования 9
2.1 Выбор языка программирования 9
2.2 Вызов сторонней программы 10
2.3 Замер времени работы пользовательской программы 11
2.4 Аргументы пользовательской программы 11
2.5 Генерация входных аргументов 12
2.6 Сериализация и десериализация аргументов 13
2.7 Разработка алгоритма 13
2.8 Выводы по главе 15
3 Разработка анализатора 16
3.1 Организация модулей программы 16
3.2 Вызов пользовательской программы 16
3.3 Пользовательские аргументы 21
3.4 Алгоритм нахождения асимптотических временных сложностей 27
3.5 Вывод в консоль 28
3.6 Выводы по главе 30
4 Тестирование и документация 31
4.1 Модульные тесты 31
4.2 Тестирование на программах 32
4.3 Документация 34
4.4 Выводы по главе 35
Заключение 37
Список использованных источников 38
Приложение А 39
Приложение Б 41
Одна из важных вещей при проектировании и разработке программного обеспечения является выбор правильного алгоритма. Неподходящий алгоритм может в разы замедлить работоспособность программы, что негативно сказывается на её использовании.
Выбор алгоритма зависит не только от обрабатываемых данных, но и от архитектуры всего приложения. Из-за этого не всегда понятна его асимптотическая сложность. Трудности с определением асимптотических сложностей можно часто увидеть у студентов начальных курсов. Данная ситуация возникает, когда студенты работают с практическими заданиями по определению асимптотических сложностей алгоритмов. Одним из решений данной проблемы может быть специальная программа или встраиваемая библиотека, которая измеряет время выполнения пользовательской программы/кода с некоторыми входными данными, и на основании полученных результатов выводит асимптотическую сложность.
В результате проделанной работы был спроектирован и разработан динамический анализатор асимптотических временных сложностей в виде программы без интерфейса. Разработанный анализатор позволяет генерировать данные, запускать пользовательскую программу и замерять её время работы на основе конфигурационного файла. Анализатор позволяет выводить наиболее распространенные асимптотические временные сложности. Для анализатора была написана документация.
Исходный код анализатора доступен для скачивания с GitHub репозитория [11].
