Оценка вычислительной сложности алгоритма

Параметры сложности алгоритмов рассматриваются в контексте времени исполнения, а также по объемам задействованных вычислительных ресурсов.
Данный вопрос имел большую актуальность актуальным на ранних стадиях развития компьютерной техники при значительных ограничениях по объёмам компьютерной памяти и другим вычислительным ресурсам (как внутренних, так и внешних). Данный вопрос имеет актуальность и в настоящее время, так как с развитием информационных технологий, проникновением их во все области жизни общества, использование компьютерной техники для решения задач из различных областей человеческой деятельности, задач, имеющих большую и очень большую размерность, проведение данного анализа приобрело принципиальный характер.
Существует классификация алгоритмов на такие, которые тратят ограниченные ресурсы памяти, и те, которым необходимо дополнительное пространство. Иногда разработчикам приходится выбирать более медленного алгоритма лишь потому, что его выполнение предполагается в ограниченных объемах памяти и не требует подключения внешних устройств.
Также актуальность расчета уровня сложности алгоритмов характерна для мобильных приложений в силу того, что мобильные устройства имеют ограниченную вычислительную мощность
Процесс оценки вычислительной сложности предполагает выполнение следующих этапов:
Шаг 1. Выбор значимых операций или группы операций.
Шаг 2. Выбор операций, содержащихся в теле алгоритма, а также операций, составляющих накладные расходы или уходящих на регистрацию и учет данных.
Входные алгоритмические операции включают:
Сравнение,
Арифметические операции.
Арифметические операции разбиваются на две группы:
Аддитивные,
мультипликативные.
Аддитивные операторы (сложения) включают сложение, вычитание, увеличение и уменьшение счетчика.
Мультипликативные операции, включающие вычисление произведения, частного, взятия остатка по модулю.
Разбиение на данные группы связано с тем, что операции умножения работают дольше, чем сложения

. На практике некоторые алгоритмы считаются более эффективными, в случае если в них меньше операций умножения, даже если количество операций сложения при этом пропорционально возрастает.
Тестирование на различных уровнях проводится на протяжении всего жизненного цикла разработки и сопровождения ПО. Уровень проведения тестирования определяет объекты тестирования: отдельные модули, группы модулей или системой в целом. Реализация тестирования на всех уровнях системы является залогом успешности реализации и сдачи проекта.
К уровням тестирования относят следующие категории [3]:
Компонентное или Модульное тестирование (Component Testing or Unit Testing)
Интеграционное тестирование (Integration Testing)
Системное тестирование (System Testing)
Приемочное тестирование (Acceptance Testing)
На рисунках 5-6 приведены диаграммы уровней тестирования.
Основные виды функциональных тестов [4]:
- тестирование по алгоритму «снизу вверх»;
- тестирование по алгоритму «сверху вниз»;
- тестирование по алгоритму большого взрыва;
Формальный процесс тестирования, который проводит проверку соответствия системы требованиям и проводится в целях [2]:
Определение на соответствие системы приемочным критериям;
Вынесение решения заказчиком или другим уполномоченным лицом решения о приемке приложения.
Приемочное тестирование производится на основании набора типичных тестовых наборов и сценариев, которые разрабатываются на основании требований к тестируемому приложению.
Решение о проведении приемочного тестирования принимается, когда:
- продукт достиг необходимого уровня качества;
- произведено ознакомление заказчика с Планом Приемочных Работ (Product Acceptance Plan) или иным документом, где описан набор действий, связанных с проведением приемочного тестирования, дата проведения, ответственные и т.д