1. Понятие алгоритма и
меры его сложности
Во всех сферах своей
деятельности, и частности в сфере обработки информации, человек сталкивается с
различными способами или методиками решения задач. Некоторые дополнительные
требования приводят к неформальному определению алгоритма:
Определение 1.1:
Алгоритм - это заданное на некотором языке конечное предписание, задающее
конечную последовательность выполнимых элементарных операций для решения
задачи, общее для класса возможных исходных данных.
Пусть D - область
(множество) исходных данных задачи, а R - множество возможных результатов,
тогда мы можем говорить, что алгоритм осуществляет отображение D ? R. Поскольку
такое отображение может быть не полным, то вводятся следующие понятия:
Алгоритм называется
частичным алгоритмом, если мы получаем результат только для некоторых d є D и
полным алгоритмом, если алгоритм получает правильный результат для всех d є D.
В теории алгоритмов
были введены различные формальные определения алгоритма и удивительным научным
результатом является доказательство эквивалентности этих формальных определений
в смысле их равномощности. Варианты словесного определения алгоритма
принадлежат российским ученым А.Н. Колмогорову и А.А. Маркову (9, стр. 24):
Определение 1.
(Колмогоров): Алгоритм - это всякая система вычислений, выполняемых по строго
определенным правилам, которая после какого-либо числа шагов заведомо приводит
к решению поставленной задачи.
Определение 2 (Марков):
Алгоритм - это точное предписание, определяющее вычислительный процесс, идущий
от варьируемых исходных данных к искомому результату.
Различные определения
алгоритма, в явной или неявной форме, постулируют следующий ряд требований
(см.5, стр. 62-63):
- алгоритм должен
содержать конечное количество элементарно выполнимых предписаний, т.е.
удовлетворять требованию конечности записи;
- алгоритм должен
выполнять конечное количество шагов при решении задачи, т.е. удовлетворять
требованию конечности действий;
- алгоритм должен быть
единым для всех допустимых исходных данных, т.е. удовлетворять требованию
универсальности;
- алгоритм должен
приводить к правильному по отношению к поставленной задаче решению, т.е.
удовлетворять требованию правильности.
Другие формальные
определения понятия алгоритма связаны с введением специальных математических
конструкций (машина Поста, машина Тьюринга, рекурсивно-вычислимые функции
Черча) и постулированием тезиса об эквивалентности такого формализма и понятия
«алгоритм» (9, стр. 25-27).
Будем рассматривать в
дальнейшем, придерживаясь определений Поста, применимые к общей проблеме,
правильные и финитные алгоритмы, т.е. алгоритмы, дающие 1-решение общей
проблемы. В качестве формальной системы будем рассматривать абстрактную машину,
включающую процессор с фон- Неймановской архитектурой, поддерживающий адресную
память и набор «элементарных» операций соотнесенных с языком высокого уровня. В
целях дальнейшего анализа примем следующие допущения:
- каждая команда
выполняется не более чем за фиксированное время;
- исходные данные
алгоритма представляются машинными словами по b битов каждое.
Конкретная проблема
задается N словами памяти, таким образом, на входе алгоритма - Nb =
N*b бит информации. Программа, реализующая алгоритм для решения общей
проблемы состоит из М машинных инструкций по bм битов - Мb =
М*b м бит информации. Кроме того, алгоритм может требовать следующих
дополнительных ресурсов абстрактной машины:d - память для хранения
промежуточных результатов;r - память для организации вычислительного процесса
(память, необходимая для реализации рекурсивных вызовов и возвратов).
При решении конкретной
проблемы, заданной N словами памяти алгоритм выполняет не более, чем конечное
количество «элементарных» операций абстрактной машины в силу условия
рассмотрения только финитных алгоритмов.
Определение 3 (2, стр.
107). Трудоёмкость алгоритма. Под трудоёмкостью алгоритма для данного
конкретного входа - Fa(N), будем понимать количество «элементарных» операций
совершаемых алгоритмом для решения конкретной проблемы в данной формальной
системе.
Комплексный анализ
алгоритма может быть выполнен на основе комплексной оценки ресурсов формальной
системы, требуемых алгоритмом для решения конкретных проблем. Очевидно, что для
различных областей применения веса ресурсов будут различны, что приводит к
следующей комплексной оценке алгоритма:
yA=c1 * Fa(N) + c2
* M + c3 * Sd + c4 * Sr, где ci - веса ресурсов.
При более детальном анализе
трудоемкости алгоритма оказывается, что не всегда количество элементарных
операций, выполняемых алгоритмом на одном входе длины N, совпадает с
количеством операций на другом входе такой же длины. Это приводит к
необходимости введения специальных обозначений, отражающих поведение функции
трудоемкости данного алгоритма на входных данных фиксированной длины (6, стр.
82-85).
Пусть DА - множество
конкретных проблем данной задачи, заданное в формальной системе. Пусть
D Î DА - задание конкретной проблемы и |D| = N.
В общем случае
существует собственное подмножество множества DА, включающее все конкретные
проблемы, имеющие мощность N:
обозначим это
подмножество через DN: DN = {DÎ DN,: |D| = N};
обозначим мощность
множества DN через MDN , т.е. MDN = |DN |.
Тогда содержательно
данный алгоритм, решая различные задачи размерности N, будет выполнять в
каком-то случае наибольшее количество операций, а в каком-то случае наименьшее
количество операций. Ведем следующие обозначения (6, стр. 77):
. FaÙ(N) - худший случай
- наибольшее количество операций, совершаемых алгоритмом А для решения
конкретных проблем размерностью N:
Ù(N) = max {Fa (D)} -
худший случай на DN
FaÚ(N) - лучший случай
- наименьшее количество операций, совершаемых алгоритмом А для решения
конкретных проблем размерностью N:
Ú(N) = min {Fa (D)} -
лучший случай на DN
Fa(N) - средний случай
- среднее количество операций, совершаемых алгоритмом А для решения конкретных
проблем размерностью N:
`Fa(N) = (1 /
MDN)*å {Fa (D)} - средний случай на DN
В зависимости от
влияния исходных данных на функцию трудоемкости алгоритма может быть предложена
следующая классификация, имеющая практическое значение для анализа алгоритмов:
.Количественно-зависимые
по трудоемкости алгоритм. Это алгоритмы, функция трудоемкости которых зависит
только от размерности конкретного входа, и не зависит от конкретных значений:
(D) = Fa (|D|) = Fa (N)
Примерами алгоритмов с
количественно-зависимой функцией трудоемкости могут служить алгоритмы для
стандартных операций с массивами и матрицами - умножение матриц, умножение
матрицы на вектор и т.д.
Параметрически-зависимые
по трудоемкости алгоритмы. Это алгоритмы, трудоемкость которых определяется не
размерностью входа (как правило, для этой группы размерность входа обычно
фиксирована), а конкретными значениями обрабатываемых слов памяти:
Fa (D) = Fa (d1,…,dn) = Fa (P1,…,Pm), m £ n
Примерами алгоритмов с
параметрически-зависимой трудоемкостью являются алгоритмы вычисления
стандартных функций с заданной точностью путем вычисления соответствующих степенных
рядов. Очевидно, что такие алгоритмы, имея на входе два числовых значения -
аргумент функции и точность, выполняют существенно зависящее от значений
количество операций.
.
Количественно-параметрические по трудоемкости алгоритмы. Однако в большинстве
практических случаев функция трудоемкости зависит как от количества данных на
входе, так и от значений входных данных, в этом случае:
(D) = Fa (||D||,
P1,…,Pm) = Fa (N, P1,…,Pm)
В качестве примера
можно привести алгоритмы численных методов, в которых параметрически-зависимый
внешний цикл по точности включает в себя количественно-зависимый фрагмент по
размерности.
. Порядково-зависимые
по трудоемкости алгоритмы. Среди разнообразия параметрически-зависимых
алгоритмов выделим еще оду группу, для которой количество операций зависит от
порядка расположения исходных объектов. Пусть множество D состоит из элементов
(d1,…,dn), и ||D||=N,
Определим Dp =
{(d1,…,dn)}-множество всех упорядоченных N-ок из d1,…,dn, отметим, что |Dp|=n!.
Если Fa (iDp) ¹ Fa (jDp), гдеiDp, jDp Î Dp, то алгоритм
будем называть порядково-зависимым по трудоемкости.
Примерами таких
алгоритмов могут служить ряд алгоритмов сортировки, алгоритмы поиска минимума и
максимума в массиве.
2. Временная и
емкостная сложность алгоритмов
В данном разделе рассмотрим
две характеристики сложности алгоритмов - временная и емкостная. Единицы
измерения сложности будем привязывать к классу архитектур наиболее
распространенных ЭВМ. Временную сложность будем подсчитывать в исполняемых
командах: количество арифметических операций, количество сравнений, пересылок
(в зависимости от алгоритма). Емкостная сложность будет определяться
количеством скалярных переменных, элементов массивов, элементов записей или
просто количеством байт.
Одно из свойств
алгоритма - массовость. В общем случае количество операций и требуемая память
зависят от исходных данных, т.е. являются функциями вектора X = (х1, х2, ...,
хn) исходных данных. С точки зрения математического анализа сложности,
сравнения алгоритмов, их классификации хотелось бы, чтобы функции сложности
(x1, x2, ..., xn) выражались в виде формул с использованием обычных,
элементарных математических функций. Тогда оказался бы доступнымбогатый арсенал
средств классической математики. Но это не всегда возможно, так как исходные
данные могут быть нечисловыми (графы, географические карты, строки символов,
звуки и т. д.). Поэтому сложность алгоритма a рассматривается как
функция от некоторого интегрированного числового параметра V, характеризующего
исходные данные. Обозначим: Ta(V) - временная сложность алгоритма a; Sa(V)
- емкостная сложность. Параметр V, характеризующий данные, называют иногда
объемом данных или сложностью данных. Оба эти термина не совсем точны. Выбор
параметра V зависит не только от вида данных, но и от вида алгоритма или от
задачи, которую этот алгоритм решает. Рассмотрим два примера.
Отыскание функций
сложности алгоритмов важно как с прикладной, так и с теоретической точек
зрения. В практике проектирования систем реального времени задача разработки
программы формулируется так: отыскать такой алгоритм a, решающий задачу P, что
Тa(X) < Tmax при X Î D, где D - область допустимых значений
входных данных (задача с ограничением на временную сложность). В системах, где
критерий качества связан с временем ожидания реакции компьютера (системы
управления базами данных, системы автоматического перевода для естественных
языков программы для игры в шахматы и другие) задача может быть поставлена так:
отыскать среди всех алгоритмов, решающих задачу Р, такой алгоритм а, для
которого функция Ta(X) будет принимать минимальные значения на выбранном
подмножестве S значений исходных данных, XÎSÌD (задача минимизации временной
сложности; дополнительно формулируются ограничения по емкостной сложности).
Двойственная задача
минимизации емкостной сложности при ограничениях на временную сложность
возникает реже в силу архитектурных особенностей современных ЭВМ, поскольку
запоминающие устройства разных уровней, входящие в состав машины, построены
так, что программе может быть доступна очень большая, практически
неограниченная область памяти - виртуальная память. Недостаточное количество
основной памяти приводит лишь к некоторому замедлению работы из-за обменов с
диском. Так как в любой момент времени программа работает лишь с двумя-тремя
значениями и
использование кэша и аппаратного просмотра команд программы вперед позволяет
заблаговременно перенести с диска в основную память нужные значения, то можно
констатировать, что минимизация емкостной сложности не является первоочередной
задачей.
3. Верхние и средние
оценки сложности алгоритмов
Многие задачи
характеризуются большим количеством исходных данных. Вводя интегральный
параметр 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ах не нарушалось никогда; в этом случае нужна оценка для худшего
случая. В других системах достаточно, чтобы это неравенство выполнялось в
большинстве случаев; тогда мы используем среднюю оценку. Опять же в связи со
свойством массовости алгоритма исследователей чаще интересуют именно средние
оценки, но получать их обычно труднее, чем верхние оценки (2, стр. 103).
