Многие задачи
характеризуются большим количеством исходных данных. Вводя интегральный
параметр V объема (сложности) данных, неявно предположено, что все множество
комбинаций значений исходных данных может быть разбито на классы. В один класс
попадают комбинации с одним и тем же значением V. Для любой комбинации из
заданного класса алгоритм будет иметь одинаковую сложность (исполнитель
выполнит одно и то же количество операций). Иначе говоря, функция c =
сложность_a(X) может быть разложена в композицию функций V= r(Х) и c = Тa(V),
где r - преобразование значений x1, x2, x3, ...,xn в значение V (8, стр.
117-119).
Но нет никаких причин
надеяться, что это будет выполняться для любых алгоритмов, учитывая наше
желание представлять функции формулами с использованием общеизвестных
элементарных функций (или, как говорят, в аналитическом виде). Выход состоит в
следующем. Множество D комбинаций исходных данных все-таки разбивается
"каким-либо разумным образом" на классы, и каждому классу
приписывается некоторое значение переменной V. Например, если мы хотим оценить
сложность алгоритма анализа арифметических выражений, то в один класс можно
поместить все выражения, состоящие из одинакового числа символов (строки
одинаковой длины) и переменную V сделать равной длине строки. Это разумное
предположение, так как с увеличением длины сложность должна увеличиваться:
припишем к выражению длины n строку +1 - получится выражение длины n+2,
требующее для анализа больше операций, чем предыдущее. Но строгого (линейного)
порядка нет. Среди выражений длины n может найтись более сложное (в смысле
анализа), чем некоторое выражение длины n+2, не говоря уже о том, что среди
выражений равной длины будут выражения разной сложности.
Затем для каждого
класса (с данным значением V) оценивается количество необходимых операций в
худшем случае, т.е. для набора исходных данных, требующих максимального
количества операций обработки (сложность для худшего случая - верхняя оценка),
и в лучшем случае - для набора, требующего минимального количества операций.
Таким образом, получаются верхняя и нижняя оценки сложности алгоритма.
Разница между Tmax(V) и
Tmin(V) может быть значительной. Но для многих алгоритмов отмечается ситуация
"редкости крайних значений": только на относительно небольшом
количестве сочетаний исходных данных реализуются близкие к верхним или нижним
оценкам значения сложности. Поэтому интересно бывает отыскать некоторое
"усредненное" по всем данным число операций (средняя оценка). Для
этого привлекаются комбинаторные методы или методы теории вероятностей.
Полученное значение и считается значением Тa(V) средней оценки.
Системы реального
времени, работающие в очень критических условиях, требуют, чтобы неравенство
Тa(X)<Tmах не нарушалось никогда; в этом случае нужна оценка для худшего
случая. В других системах достаточно, чтобы это неравенство выполнялось в
большинстве случаев; тогда мы используем среднюю оценку. Опять же в связи со
свойством массовости алгоритма исследователей чаще интересуют именно средние
оценки, но получать их обычно труднее, чем верхние оценки.
В информатике и теории
алгоритмов вычислительная сложность алгоритма
— это функция, определяющая зависимость объёма работы, выполняемой некоторым
алгоритмом, от размера входных данных. Раздел, изучающий вычислительную
сложность, называется теорией сложности вычислений. Объём работы обычно
измеряется абстрактными понятиями времени и пространства,
называемыми вычислительными ресурсами. Время определяется количеством
элементарных шагов, необходимых для решения задачи, тогда как пространство
определяется объёмом памяти или места на носителе данных. Таким образом, в
этой области предпринимается попытка ответить на центральный вопрос разработки
алгоритмов: «как изменится время исполнения и объём занятой памяти в
зависимости от размера входа и выхода?». Здесь под размером входа понимается
длина описания данных задачи в битах(например, в задаче
коммивояжёра длина входа пропорциональна количеству городов и дорог между
ними), а под размером выхода — длина описания решения задачи (наилучшего
маршрута в задаче коммивояжера).
