Виды и методы вычисления сложности алгоритма

добавление одного бита к входным данным удвоит время выполнения алгоритма.

Обычно алгоритмы классифицируются в соответствии с их временной или пространственной сложностью. Алгоритм называют постоянным, если его сложность не зависит от п: 0(1). Алгоритм является линейным, если его временная сложность О(n). Алгоритмы могут быть квадратичными, кубическими и т.д. Все эти алгоритмы - полиномиальны, их сложность - О(ш), где ш - константа. Алгоритмы с полиномиальной временной сложностью называются алгоритмами с полиномиальным временем

Алгоритмы, сложность которых равна 0(tf(n)), где t - константа, большая, чем 1, a f(n) - некоторая полиномиальная функция от п, называются экспоненциальными. Подмножество экспоненциальных алгоритмов, сложность которых равна 0(cf(n)), где где с - константа, a f(n) возрастает быстрее, чем постоянная, но медленнее, чем линейная функция, называется суперполиномиальным.

В идеале, криптограф хотел бы утверждать, что алгоритм, лучший для взлома спроектированного алгоритма шифрования, обладает экспоненциальной временной сложностью. На практике, самые сильные утверждения, которые могут быть сделаны при текущем состоянии теории вычислительной сложности, имеют форму "все известные алгоритмы вскрытия данной криптосистемы обладают суперполиномиальной временной сложностью". То есть, известные нам алгоритмы вскрытия обладают суперполиномиальной временной сложностью, но пока невозможно доказать, что не может быть открыт алгоритм вскрытия с полиномиальной временной сложностью. Развитие теории вычислительной сложности возможно когда- нибудь позволит создать алгоритмы, для которых существование алгоритмов с полиномиальным временем вскрытия может быть исключено с математической точностью.

С ростом n временная сложность алгоритмов может стать настолько огромной, что это повлияет на практическую реализуемость алгоритма. 

 

При условии, что единицей времени для нашего компьютера является микросекунда, компьютер может выполнить постоянный алгоритм за микросекунду, линейный - за секунду, а квадратичный - за 11.6 дня. Выполнение кубического алгоритма потребует 32 тысяч лет, что в принципе реализуемо, компьютер, конструкция которого позволила бы ему противостоять следующему ледниковому периоду, в конце концов, получил бы решение. Выполнение экспоненциального алгоритма тщетно, независимо от экстраполяции роста мощи компьютеров, параллельной обработки или контактов с инопланетным суперразумом.

Взглянем на проблему вскрытия алгоритма шифрования грубой силой. Временная сложность такого вскрытия пропорциональна количеству возможных ключей, которое экспоненциально зависит от длины ключа. Если п - длина ключа, то сложность вскрытия грубой силой равна 0(2п). Сложность вскрытия грубой силой при 56-битовом ключе составляет 256, а при 112-битовом ключе - 2112. В первом случае вскрытие возможно, а во втором - нет.

 

 

 

 

 

 

1.3. Верхние и средние оценки сложности алгоритмов

Многие задачи характеризуются большим количеством исходных данных. Вводя интегральный параметр V объема (сложности) данных, неявно предположено, что все множество комбинаций значений исходных данных может быть разбито на классы. В один класс попадают комбинации с одним и тем же значением V. Для любой комбинации из заданного класса алгоритм будет иметь одинаковую сложность (исполнитель выполнит одно и то же количество операций). Иначе говоря, функция с = сложность а(Х) может быть разложена в композицию функций V= г(Х) и с = Ta(V), где г - преобразование значений xl, х2, хЗ, ...,хn в значение V.²

Но нет никаких причин надеяться, что это будет выполняться для любых алгоритмов, учитывая наше желание представлять функции формулами с использованием общеизвестных элементарных функций (или, как говорят, в аналитическом виде). Выход состоит в следующем. Множество D комбинаций исходных данных все-таки разбивается "каким- либо разумным образом" на классы, и каждому классу приписывается некоторое значение переменной V. Например, если мы хотим оценить сложность алгоритма анализа арифметических выражений, то в один класс можно поместить все выражения, состоящие из одинакового числа символов (строки одинаковой длины) и переменную V сделать равной длине строки. Это разумное предположение, так как с увеличением длины сложность должна увеличиваться: припишем к выражению длины n строку +1 - получится выражение длины n+2, требующее для анализа больше операций, чем предыдущее. Но строгого (линейного) порядка нет. Среди выражений длины п может найтись более сложное (в смысле анализа), чем некоторое выражение длины n+2, не говоря уже о том, что среди выражений равной длины будут выражения разной сложности.

Затем для каждого класса (с данным значением V) оценивается количество необходимых операций в худшем случае, т.е. для набора исходных данных, требующих максимального количества операций обработки (сложность для худшего случая - верхняя оценка), и в лучшем случае - для набора, требующего минимального количества операций. Таким образом, получаются верхняя и нижняя оценки сложности алгоритма (рисунок 1).

 

Рис.1 Зависимость сложности алгоритма от сложности данных

Разница между T max (V) и T min (V) может быть значительной. Но для многих алгоритмов отмечается ситуация «редкости крайних значений»: только на относительно небольшом количестве сочетаний исходных данных реализуются близкие к верхним  или нижним оценкам сложности. Поэтому интересно бывает отыскать некоторое «усредненное» по всем данным число операций (средняя оценка). Для этого привлекаются комбинаторные методы или методы теории вероятностей. Полученное значение и считается значением Тα(V) средней оценки.

Системы реального времени, работающие в очень критических условиях, требуют, чтобы неравенство Тα(X)˂ T max не нарушалось никогда; в этом случае нужна оценка для худшего. В других системах достаточно, чтобы это неравенство выполнялось в большинстве случаев; тогда мы используем среднюю оценку. Опять же в связи со свойством массовости алгоритма исследователей чаще интересуют именно средние оценки, но получать их обычно труднее, чем верхние оценки.

ВИДЫ И МЕТОДЫ ВЫЧИСЛЕНИЯ СЛОЖНОСТИ АЛГОРИТМА 2.1.Основные методы и приемы анализа сложности

Отыскание функции сложности производится на основе анализа текста алгоритма. Для определенности будем считать, что алгоритм записан на универсальном языке программирования типа Паскаля и содержит явно записанные арифметические операции, операции сравнения и пересылки скалярных данных, управляющие конструкции циклов и выбора. Если встречаются вызовы процедур, то вызов не рассматривается как одна операция: вызов вносит вклад в общую сумму на основе подсчета количества операций в вызываемой процедуре, плюс собственно оператор вызова (с единичной сложностью). С целью анализа алгоритм (программу) удобно представлять управляющим графом (родственное понятие - схема алгоритма). Управляющий граф строится следующим образом. Каждому оператору присваивания или вызову процедуры ставится в соответствие вершина графа (точка). Два последовательно записанных оператора (последовательно исполняемых) изображаются вершинами, соединенными стрелкой, указывающей порядок исполнения (рис. 2).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис.2. Граф линейного участка Последовательность из нескольких операторов присваивания или вызовов процедур изображается цепью и называется линейным участком. Условный оператор изображается вершиной, соответствующей вычислению условия, и двумя выходящими дугами с приписанными им вариантами then, else.

if а < b then х := а else х := b;Если после then записан составной оператор (линейный участок), то в управляющем графе ему соответствует цепь. Условный оператор задает разветвление в управляющем графе, заканчивающееся пустой вершиной (без операций), помеченной точкой с запятой. Если в операторе часть else отсутствует, то нижняя ветка включает пустую вершину.³ Подобный фрагмент в управляющем графе порождает оператор выбора case, но только разветвление может быть на большее число ветвей и выходящие дуги помечаются соответствующими константами (рис.3). 

Операторы цикла (рисунок 3) изображаются в управляющем графе замкнутой последовательностью вершин (циклом).

Рис.3. Графы операторов цикла

 

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

Необходимо рассмотреть следующие несколько случаев.

Управляющий граф представляет собой линейный участок. Сложность равна сумме весов вершин, принадлежащих линейному участку, и является константой, если на участке нет вершин - вызовов процедур. Если такие вершины есть, то их вес равен функциям сложности соответствующих процедур. 

Управляющий граф содержит разветвления, но не содержит циклов. Это означает, что вычислительный процесс в зависимости от исходных данных может направиться по одной из конечного числа ветвей, начинающихся в начальной вершине и заканчивающихся в одной из конечных вершин. Расчет функции сложности зависит от того, рассматривается худший случай или средний случай.

Управляющий граф содержит цикл, порожденный оператором for. Если выражения, определяющие начальное и конечное значения параметра цикла суть константы, то нетрудно подсчитать, сколько раз будет выполняться тело цикла и умножить на этот коэффициент вес тела цикла. Если выражения зависят от исходных данных, то можно оценить значение разности этих выражений в худшем или среднем случаях.

Управляющий граф содержит цикл, порожденный операторами while или repeat. Циклы while и repeat могут вызвать больше затруднений при анализе, чем оператор for, так как количество исполнений тела цикла зависит от истинности или ложности условия, а переменные, входящие в состав условия изменяются в теле цикла, причем оценить величину и направленность этого изменения достаточно сложно.

Управляющий граф содержит разветвлении. Для худшего случая нужно вычислить вес каждой ветви как сумму весов входящих в нее вершин, после чего найти максимальный из весов ветвей. Это и будет сложностью процедуры.

Пример 1. Управляющий граф содержит 10 вершин с весом {3, 5, 1,4, 3, 4, 6, 8, 5, 3}. Вершина 3 (вес равен 1) соответствует вычислению условия в операторе if; вершины 4, 5, 6 входят в часть then, вершины 7, 8 входят в часть else. Таким образом, имеется две ветви с весом 3+5+1+4+3+4+5+3 = 28 и 3+5+1+6+8+5+3 = 31; сложность равна 31.

Пример 2. Тот же граф, что и в примере 1, но вершина 8 соответствует вызову процедуры, имеющей сложность 2V + 1. В этом случае функция сложности равна max (28, 2V+24 ) = 24+max(4, 2V) = 24 + 2 max ( 2, V ).

Для среднего случая, кроме веса ветвей, нужно оценить еще и частоты ветвей. Под частотой ветви понимается отношение числа выполнений программы, при которых исполнялись операторы, принадлежащие данной ветви, к общему числу выполнений программы. Тогда сложность программы будет вычисляться как сумма произведений весов ветвей на их частоты.⁴Если все комбинации исходных данных программы равновероятны, то частоты ветвей можно оценить следующим образом:

Пусть управляющий граф содержит разветвления с условиями CI, С2, СЗ, ..., Сп, причем проверка условия С1 производится всегда первой по ходу выполнения программы. Следовательно, условие С1 разбивает все ветви на две группы: для ветвей первой группы это условие истинно, а для ветвей второй группы - ложно. Условие С2 разбивает группу ветвей с истинным условием С1 на две группы, удовлетворяющие условиям CI and С2 и CI and not С2. Условие СЗ порождает группы ветвей, удовлетворяющих условиям not CI and СЗ и not CI and not СЗ и т. д. Множество D комбинаций исходных данных также делится на две части D1 и D2 и это деление порождается условием С1 даже, если сами исходные данные не входят в формулировку условия, а входят только константы и промежуточные переменные. В свою очередь, D1 делится на подмножества D2 и D3 в соответствии с условием С2 и так далее. На рисунке 1 изображены примеры управляющего графа программы и разбиений областей D. Три условных оператора изображены черными вершинами, область D делится сначала сплошной линией на подобласти D1 и D2, а затем каждая из них делится пунктирными линиями на подобласти D3, D4 и D5, D6.

 

 

 

 Рис.4 Управляющий граф и разбиение области данных

Каждая подобласть, не разделенная на более мелкие части, соответствует одной ветви в управляющем графе. Обозначим все такие области di. Тогда, считая все комбинации исходных данных равновероятными, можем оценить частоту исполнения і-й ветви как отношение мощности множества di к мощности множества D, pi = |di|/[D|. Если і-я ветвь имеет вес И то сложность программы можно оценить величиной

, где k - количество ветвей.

 

Пример 3. Тот же граф, что и в примере 1. Условие в операторе if имеет вид (х<0,5), где х - входная переменная, значения которой принадлежат интервалу [0,1]. Если более подробной информации о входной переменной нет, то можно предполагать, что вероятность получить на входе значение хе [0, 0,5] равна вероятности получить х є [0,5, 1] и, значит та и другая вероятности равны 0,5. Следовательно, и вероятности ветвей одинаковы; средняя сложность равна 28(1/2) + 31(1/2) = 29,5 .