Анализ сложности алгоритма

Введение
Традиционно в программировании понятие алгоритмической сложности связано с использованием ресурсов компьютера. То есть процессорное время, необходимое для выполнения программы, потребление машинной памяти и так далее. Память обычно описывается с точки зрения количества данных, игнорируя память, используемую для записи программных команд. Время рассчитывается в относительных единицах, поэтому эта оценка должна, по возможности, быть одинаковой для машин с разной тактовой частотой и немного отличающейся архитектурой.
Этот подход развивался исторически и ориентирован в первую очередь на научные и инженерные приложения теории алгоритмов. Объем данных значительно превышает размер самой программы, и программа может работать часами. Если в научных и инженерных приложениях длительное время вычислений приносит только неудобства пользователям, то во многих других областях ресурсы настолько критичны, что с общим удобством проекта из-за неэффективной работы программы могут возникнуть проблемы. К таким областям относятся системы реального времени. Это компьютерные системы, которые управляют реальными процессами или обрабатывают информацию, используемую для принятия оперативных решений.
В этой статье мы подробно исследуем два ее свойства алгоритмической сложности: темпоральную и емкостную. Однако здесь не обсуждается текстовая сложность (длина) алгоритма. Это потому, что она характеризует исполнителя (машину), его язык, а не то, как он решает задачу. Не описывает он и логическую сложность разработки алгоритма, т.е. сколько месяцев уходит на написание программы, поскольку дать объективные количественные характеристики невозможно. Оба относятся к области компьютерных наук, называемой «технологиями программирования» .



1. Понятие алгоритмов и мер их сложности.

Во всех сферах своей деятельности, особенно в обработке информации, человек сталкивается с разными методами или способами решения задач. Некоторые дополнительные требования приводят к неформальному определению алгоритма.
Определение 1.1: Алгоритм — это конечное предписание, данное на языке, который определяет конечную последовательность допустимых элементарных операций для решения проблемы, общей для класса возможных исходных данных.
Будем говорить, что алгоритм реализует отображение D → R, где D — область (множество) исходных данных задачи, а R — множество возможных результатов. Такие отображения могут быть несовершенными, поэтому вводятся следующие понятия:
Алгоритм называется частичным, если он дает результаты только для некоторого d + D, и полным алгоритмом, если он дает правильные результаты для всех d + D.
Теория алгоритмов ввела различные формальные определения алгоритмов, и удивительные научные результаты доказывают, что эти формальные определения эквивалентны в смысле равной мощности. Вариант устного определения алгоритма принадлежит русскому ученому А.Н. Колмогоров и А.А. Марков .
Определение 1. (Колмогоров): Алгоритм — это система вычислений, выполняемых по строго определенным правилам, которые через определенное число шагов приводят к решению задачи.
Определение 2 (Марков): Алгоритм — это точное предписание, которое определяет вычислительный процесс от ввода переменных до достижения желаемого результата.