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

Размещено на http://www.allbest.ru/

Содержание

• Введение
• 1. Понятие алгоритма и меры его сложности
• 2. Временная и емкостная сложность алгоритмов
• 3. Верхние и средние оценки сложности алгоритмов
• 4. Основные методы и приемы анализа сложности
• 5. Анализ сложности рекурсивных алгоритмов
• 6. Оптимизация алгоритмов
• Заключение
• Список использованной литературы

Введение

Традиционно в программировании понятие сложности алгоритма связано с использованием ресурсов компьютера: насколько много процессорного времени требует программа для своего выполнения, насколько много при этом расходуется память машины? Учет памяти обычно ведется по объему данных и не принимается во внимание память, расходуемая для записи команд программы. Время рассчитывается в относительных единицах так, чтобы эта оценка, по возможности, была одинаковой для машин с разной тактовой частотой и с незначительными вариациями в архитектуре.

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

В данной работе будут подробно рассмотрены две характеристики сложности алгоритмов - временная и емкостная. Но не будем обсуждать сложность (длину) текста алгоритма, поскольку она больше характеризует исполнителя (машину), его язык, а не метод решения задачи. Не будем также обсуждать логическую сложность разработки алгоритма - сколько человеко-месяцев нужно потратить на создание программы, поскольку не представляется возможным дать объективные количественные характеристики. Обе эти темы относятся к области компьютерных наук, называемой "технология программирования" (software engineering).

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

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

Определение 1.1: Алгоритм - это заданное на некотором языке конечное предписание, задающее конечную последовательность выполнимых элементарных операций для решения задачи, общее для класса возможных исходных данных.

Пусть D - область (множество) исходных данных задачи, а R - множество возможных результатов, тогда мы можем говорить, что алгоритм осуществляет отображение D > R. Поскольку такое отображение может быть не полным, то вводятся следующие понятия:

Алгоритм называется частичным алгоритмом, если мы получаем результат только для некоторых d є D и полным алгоритмом, если алгоритм получает правильный результат для всех d є D.

В теории алгоритмов были введены различные формальные определения алгоритма и удивительным научным результатом является доказательство эквивалентности этих формальных определений в смысле их равномощности. Варианты словесного определения алгоритма принадлежат российским ученым А.Н. Колмогорову и А.А. Маркову (9, стр. 24):

Определение 1. (Колмогоров): Алгоритм - это всякая система вычислений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.

Определение 2 (Марков): Алгоритм - это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.

Различные определения алгоритма, в явной или неявной форме, постулируют следующий ряд требований (см.5, стр. 62-63):

-- алгоритм должен содержать конечное количество элементарно выполнимых предписаний, т.е. удовлетворять требованию конечности записи;

-- алгоритм должен выполнять конечное количество шагов при решении задачи, т.е. удовлетворять требованию конечности действий;

-- алгоритм должен быть единым для всех допустимых исходных данных, т.е. удовлетворять требованию универсальности;

-- алгоритм должен приводить к правильному по отношению к поставленной задаче решению, т.е. удовлетворять требованию правильности.

Другие формальные определения понятия алгоритма связаны с введением специальных математических конструкций (машина Поста, машина Тьюринга, рекурсивно-вычислимые функции Черча) и постулированием тезиса об эквивалентности такого формализма и понятия «алгоритм» (9, стр. 25-27).

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

-- каждая команда выполняется не более чем за фиксированное время;

-- исходные данные алгоритма представляются машинными словами по битов каждое.

Конкретная проблема задается N словами памяти, таким образом, на входе алгоритма - N = N* бит информации. Программа, реализующая алгоритм для решения общей проблемы состоит из М машинных инструкций по м битов - М = М* м бит информации. Кроме того, алгоритм может требовать следующих дополнительных ресурсов абстрактной машины:

Sd - память для хранения промежуточных результатов;

Sr - память для организации вычислительного процесса (память, необходимая для реализации рекурсивных вызовов и возвратов).

При решении конкретной проблемы, заданной N словами памяти алгоритм выполняет не более, чем конечное количество «элементарных» операций абстрактной машины в силу условия рассмотрения только финитных алгоритмов.

Определение 3 (2, стр. 107). Трудоёмкость алгоритма. Под трудоёмкостью алгоритма для данного конкретного входа - Fa(N), будем понимать количество «элементарных» операций совершаемых алгоритмом для решения конкретной проблемы в данной формальной системе.

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

c1 * Fa(N) + c2 * + 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):

1. Fa(N) - худший случай - наибольшее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N:

Fa(N) = max {Fa (D)} - худший случай на DN

2. Fa(N) - лучший случай - наименьшее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N:

Fa(N) = min {Fa (D)} - лучший случай на DN

3. Fa(N) - средний случай - среднее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N:

Fa(N) = (1 / MDN)* {Fa (D)} - средний случай на DN

В зависимости от влияния исходных данных на функцию трудоемкости алгоритма может быть предложена следующая классификация, имеющая практическое значение для анализа алгоритмов:

1.Количественно-зависимые по трудоемкости алгоритм. Это алгоритмы, функция трудоемкости которых зависит только от размерности конкретного входа, и не зависит от конкретных значений:

Fa (D) = Fa (|D|) = Fa (N)

Примерами алгоритмов с количественно-зависимой функцией трудоемкости могут служить алгоритмы для стандартных операций с массивами и матрицами - умножение матриц, умножение матрицы на вектор и т.д.

2.Параметрически-зависимые по трудоемкости алгоритмы. Это алгоритмы, трудоемкость которых определяется не размерностью входа (как правило, для этой группы размерность входа обычно фиксирована), а конкретными значениями обрабатываемых слов памяти:

Fa (D) = Fa (d1,…,dn) = Fa (P1,…,Pm), m n

Примерами алгоритмов с параметрически-зависимой трудоемкостью являются алгоритмы вычисления стандартных функций с заданной точностью путем вычисления соответствующих степенных рядов. Очевидно, что такие алгоритмы, имея на входе два числовых значения - аргумент функции и точность, выполняют существенно зависящее от значений количество операций.

3. Количественно-параметрические по трудоемкости алгоритмы. Однако в большинстве практических случаев функция трудоемкости зависит как от количества данных на входе, так и от значений входных данных, в этом случае:

Fa (D) = Fa (||D||, P1,…,Pm) = Fa (N, P1,…,Pm)

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

4. Порядково-зависимые по трудоемкости алгоритмы. Среди разнообразия параметрически-зависимых алгоритмов выделим еще оду группу, для которой количество операций зависит от порядка расположения исходных объектов. Пусть множество 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) выражались в виде формул с использованием обычных, элементарных математических функций. Тогда оказался бы доступнымбогатый арсенал средств классической математики. Но это не всегда возможно, так как исходные данные могут быть нечисловыми (графы, географические карты, строки символов, звуки и т. д.). Поэтому сложность алгоритма рассматривается как функция от некоторого интегрированного числового параметра V, характеризующего исходные данные. Обозначим: T(V) - временная сложность алгоритма ; S(V) - емкостная сложность. Параметр V, характеризующий данные, называют иногда объемом данных или сложностью данных. Оба эти термина не совсем точны. Выбор параметра V зависит не только от вида данных, но и от вида алгоритма или от задачи, которую этот алгоритм решает. Рассмотрим два примера.

Отыскание функций сложности алгоритмов важно как с прикладной, так и с теоретической точек зрения. В практике проектирования систем реального времени задача разработки программы формулируется так: отыскать такой алгоритм a, решающий задачу P, что Т(X) < Tmax при X D, где D - область допустимых значений входных данных (задача с ограничением на временную сложность). В системах, где критерий качества связан с временем ожидания реакции компьютера (системы управления базами данных, системы автоматического перевода для естественных языков программы для игры в шахматы и другие) задача может быть поставлена так: отыскать среди всех алгоритмов, решающих задачу Р, такой алгоритм а, для которого функция T(X) будет принимать минимальные значения на выбранном подмножестве S значений исходных данных, XSD (задача минимизации временной сложности; дополнительно формулируются ограничения по емкостной сложности).

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

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

Многие задачи характеризуются большим количеством исходных данных. Вводя интегральный параметр V объема (сложности) данных, неявно предположено, что все множество комбинаций значений исходных данных может быть разбито на классы. В один класс попадают комбинации с одним и тем же значением V. Для любой комбинации из заданного класса алгоритм будет иметь одинаковую сложность (исполнитель выполнит одно и то же количество операций). Иначе говоря, функция c = сложность_(X) может быть разложена в композицию функций V= r(Х) и c = Т(V), где r - преобразование значений x1, x2, x3, ...,xn в значение V (8, стр. 117-119).

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

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

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

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

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

4. Основные методы и приемы анализа сложности

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



Рис.2. Граф линейного участка

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

if a < b then x := а

else x := b;

Рис.3. Граф условного оператора

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



Рис.4. Граф оператора разветвления

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

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

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

Необходимо рассмотреть следующие несколько случаев (6, стр. 172-178):

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

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

Управляющий граф содержит цикл, порожденный оператором 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 ).

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

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



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

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

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

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

Пример 4 (объединение условий примеров 2 и 3). Средняя сложность равна 28(1/2) + (2V + 24)(1/2) = V + 26.

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

Пример 5. Процедура содержит цикл

for i := 1 to x do

<тело цикла>,

где x - входная переменная, x[1,100]. Тело цикла выполняется x раз, худший случай реализуется при x=100. Если предположить равновероятность различных значений x, то среднее количество выполнений тела цикла равно (1/100)(1+2+3+ ...+100)=50,5.

Пример 6. Процедура содержит вложенные циклы:

for i := 1 to x do

for j := i to x do

<тело цикла>;

входная переменная x[1, 5]. Тело цикла выполняется x + (x-1)+(х-2)+ ...+ 1 = x (х+1)/2 раз. Верхняя граница сложности = max = (x (х+1)/2) = 13. Среднее значение сложности подсчитать несколько труднее. Снова положим, что все 5 возможных значений x равновероятны. Тогда среднее значение сложности равно:

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

Рассмотрим в качестве примера (4, стр. 334) вычисление методом Ньютона (имеется в виду вычисление вещественного значения корня). Задача сводится к нахождению корня уравнения x(1/p) - z = 0, который, в свою очередь, отыскивается с помощью итерационного процесса

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

function P_root( p: integer; x, z0, epsilon: real ): real;

var

i: integer;

old, z: real;

begin

z := z0;

repeat

old := z;

у := old;

for i:= 2 to p - 1 do у:= y*old;

z := (p - l)*old/p + x/ (p*y);

until abs( z - old ) < epsilon;

end;

Из теории численных методов известно, что требуемое количество n итераций для достижения заданной точности имеет порядок . Этот процесс сходится (заканчивается) очень быстро: уже при 5 итерациях достигается точность выше 10-9.

В общем случае условие в операторе while или в операторе repeat делит область комбинаций исходных и промежуточных данных, т.е. область возможных состояний программы на момент начала исполнения оператора цикла на две части: для первой условие выполняется, а для второй - нет. Если начальное состояние принадлежит первой подобласти (для while) или второй подобласти (для repeat), то с каждым выполнением тела цикла состояние (как точка в пространстве состояний) будет перемещаться по некоторой траектории, зависящей от операций, заданных в теле, до тех пор, пока не пересечет границу области. Именно количество шагов до пересечения границы и определяет сложность этого участка программы.

5. Анализ сложности рекурсивных алгоритмов

Рассмотрим сначала случай прямой рекурсии с единственным (вне какого-либо цикла) рекурсивным вызовом в теле процедуры. Примером такого алгоритма является алгоритм Евклида вычисления наибольшего общего делителя. Текст рекурсивной процедуры с вектором исходных данных X содержит вызов этой же процедуры с измененным по некоторому правилу вектором исходных данных Y = f(X). Кроме этого, в тексте содержится некоторое нерекурсивное вычисление h(X) и операции сравнения c(Х,S) значения X со значением S, при котором рекурсивный процесс должен заканчиваться. Обозначим "точное" (а не верхнюю границу или среднее) значение сложности при входных данных X через Т(X). Тогда

Т(X) = Т(Y)+Th(X)+Tc(X,S), или Т(X) = Т(АХ))+Tf(X)+Th(X)+ Tc(X,S).

Второе соотношение представляет собой рекуррентное уравнение для определения значений неизвестной функции Т(X) через известные значения f(A), Tf(X), Th(X), Tc(X,S). Кроме этого, имеется начальное условие T(S)=Ts(S) с известной функцией сложности вычисления (нерекурсивного) значения S. Таким образом, имеется система:

Т(Х) =T(f(X))+ Tf(X)+Th(X)+ Тc(X, S)

T(S)=Tc(S,S)+Ts(S)

Это частный случай рекуррентного уравнения. Такие уравнения имеют развитую теорию. В некоторых случаях возможно аналитическое решение. Покажем его применение на примере рекурсивного вычисления факториала:

function FACTORIAL (х: integer): integer;

begin

if x = 1 then FACTORIAL:= 1

else FACTORIAL:= x * FACTORIAL (x-1);

end;

Здесь X=x, S=1, f(X)=X-1, Tf(X)=1, Th(X) = 2, Tc(X,S)=l, Ts(S) = 1. Таким образом, система уравнений превращается в Т(x) = Т(х-1)+4, Т(1) = 2. Ее решение - Т(x) = 4х-2.

Верхняя оценка Т(V) может быть получена подобным образом, но с использованием рекуррентных неравенств:

Т(V) <= Т(f(V))+Tf(V)+Th(V)+Tc(V,V0),

T(V0) <= Tc(V0, Vo)+Ts(V0).

Оценка среднего значения сложности требует учета вероятностных законов и может быть значительно более трудной. Вообще говоря, нельзя использовать написанные выше рекуррентные уравнения в вероятностном случае: среднее значение функции случайной величины не равно значению функции от среднего значения случайной величины, среднее (f(X)) <> f(среднее (X)), кроме случая линейной функции f.

Теперь рассмотрим более общий случай прямой рекурсии (4, стр. 402-404) с несколькими рекурсивными вызовами в теле процедуры. Эти вызовы могут иметь разные аргументы Y1, Y2, . . . ,Yk, где Y1 =fl(X), Y2 =f2(X), ..., Yk=fk(X). Рекуррентное уравнение для функции сложности имеет вид

Т(X) = Т(f1(X)) + Т(f2(X)) + ... + Т?(fk(X)) + Tf1(X) + Тf2(X) + ...+Тfk(X) + Тh (X) + Tc (X, S)

Т(S) = Tc (S, S) + Ts (S).

6. Оптимизация алгоритмов

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

Во-первых, сложно сформулировать критерий оптимизации, имеющий одновременно и бесспорное практическое значение и однозначно определенный в математическом плане. Например, можно поставить задачу минимизации числа команд машины Тьюринга - критерий, хорошо определенный математически; но совсем неясно его практическое значение, поскольку вряд ли реальная программа на реальном компьютере будет моделировать машину Тьюринга. Можно поставить задачу минимизации времени выполнения программы на реальной машине - ясный с практической точки зрения критерий. Однако невозможно будет решить задачу оптимизации математическими методами, так как время выполнения зависит (иногда значительно) от архитектуры ЭВМ, а архитектуру современных компьютеров не опишешь небольшим числом параметров. Важно также, что программа, работающая быстрее других на одном компьютере, может оказаться не самой быстрой на другом. Существуют даже специальные программы с общим названием benchmark, предназначенные для оценки архитектур.

Во-вторых, не совсем ясно, что такое сложность задачи. Ее можно было бы определить как минимальную из сложностей алгоритмов, решающих эту задачу. Но существует ли алгоритм минимальной сложности (как убедиться, что найденный алгоритм действительно минимальный или, напротив, не минимальный)? Есть ли к чему стремиться? И насколько труден поиск этого минимума? Эти вопросы связаны с нижней оценкой сложности алгоритмов (а не верхней, как в предыдущих шагах) (5, стр. 89-92).

Можно ли для рассматриваемой задачи доказать, что никакой решающий ее алгоритм не может быть проще этой нижней оценки? Возьмем известную задачу перемножения квадратных матриц. Приведен алгоритм сложности Т(n) = 3n3 + n2. (8, стр. 199-203) Вероятно, это не лучший алгоритм, но какова оценка снизу? Результирующая матрица имеет n2 элементов. Для вычисления любого элемента нужна хотя бы одна операция однопроцессорной машины - два элемента за одну операцию найти нельзя. Для минимального алгоритма мы получаем неравенства n2 <= T, min(n) <= 3n3+n2 . Вряд ли n2 - хорошая нижняя оценка, но уже известно, что n3 нижней оценкой не является, так как найдены более быстрые алгоритмы (в частности, алгоритм Штрассена). (8, стр. 211)

Существует несколько самостоятельных аспектов оптимизации программ, из которых выделим два:

-- оптимизация, связанная с выбором метода построения алгоритма;

-- оптимизация, связанная с выбором методов представления данных в программе.

Первый вид оптимизации имеет глобальный характер и ведет к уменьшению порядка функции сложности - например, замена алгоритма с Т(V) = O(FS) на алгоритм с T(V) = O(V4). Он зависит от того, как задача разбивается на подзадачи, насколько это разбиение свойственно самой задаче или является только искусственным приемом. Общим руководящим подходом здесь может быть последовательность действий, обратная анализу алгоритмов. При анализе по рекурсивному алгоритму строится уравнение, которое затем решается. При оптимизации реализуется цепочка:

Формула, задающая желаемую сложность ->

Соответствующее уравнение (одно из возможных) ->

Метод разбиения задачи на подзадачи.

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

Оба вида оптимизации дополняют друг друга и могут применяться совместно.

Заключение

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

Разработанные в 1930-х годах разнообразные формальные модели алгоритмов (Пост, Тьюринг, Черч), равно как и предложенные в 1950-х годах модели Колмогорова и Маркова, оказались эквивалентными в том смысле, что любой класс проблем, разрешимых в одной модели, разрешимы и в другой.

В настоящее время полученные на основе теории алгоритмов практические рекомендации получают всё большее распространение в области проектирования и разработки программных систем.

Одна из задач, которая обычно ставится при разработке алгоритмов и программ - минимизация требуемых программой ресурсов. Особенно это касается системного программного обеспечения: программ операционной системы, трансляторов, систем управления базами данных и знаний и т. д., т.е. программ, имеющих большое количество пользователей и испытывающих как товар, большую конкуренцию на рынке программных средств.

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

Однако по-прежнему открыты вопросы, связанные со сводимостью алгоритмов друг к другу и остается нерешенной известная проблема P=NP.

алгоритм сложность оптимизация

Список использованной литературы

1. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы: Пер. с англ.: - М.: Издательский дом «Вильямс», 2001 г. -384 с., ил.

2. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. - 2-ое изд., испр. - СПб.: Невский диалект, 2001 г. - 352 с., ил.

3. Карпов Ю.Г. Теория автоматов - СПб.: Питер, 2002 г. - 224с., ил.

4. Кнут Д. Искусство программирования. Тома 1, 2, 3. 3-е изд. Пер. с англ. : Уч. пос. - М.: Изд. дом "Вильямс", 2001 г.

5. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. - М.: МЦНМО, 2001 г. - 960 с., 263 ил.

6. Макконнел Дж. Анализ алгоритмов. Вводный курс. - М.: Техносфера, 2002 г. -304 с.

7. Новиков Ф. А. Дискретная математика для программистов. - СПб.: Питер, 2001 г. - 304 с., ил.

8. Романовский И.В. Дискретный анализ. Учебное пособие для студентов, специализирующихся по прикладной математике. - Издание 2-ое, исправленное. - СПб.; Невский диалект, 2000 г. - 240 с., ил.

9. Успенский В.А. Машина Поста. - М.: Наука, 1999 г. - 96 с.

Размещено на Allbest.ru