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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

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

Второе соотношение представляет собой рекуррентное уравнение для определения значений неизвестной функции Та(Х) через известные значения f(A), Tf(X), Th(X), Tc(X,S). Кроме этого, имеется начальное условие Ta(S)=Ts(S) с известной функцией сложности вычисления (нерекурсивного) значения S. Таким образом, имеется система: Ta(X) =Tot(f(X))+ Tf(X)+Th(X)+ Тс(Х, S) Ta(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=l, f(X)=X-l, Tf(X)=l, Th(X) = 2, Tc(X,S)=l, Ts(S) = 1. Таким образом, система уравнений превращается в Та(х) = Та(х-1)+4, Та(1) = 2. Ее решение - Тα(х) = 4х-2.

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

Tα(V) <= Tα(f(V))+Tf(V)+Th(V)+Tc(V,VO), Tα(VO) <= Tc(V0, Vo)+Ts(V0).

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

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

Tα(X) = Ta(fl(X)) + Ta(f2(X)) + ... + TaD(fk(X)) + Tfl(X) + Tf2(X) + ...+Tfk(X) + Th (X) + Тс (X, S)

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

 

 

 

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

 

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

Битюцкий В.Н. Теория алгоритмов.-М.,2010.

ВиртН. Алгоритмы и структуры данных.-М.,2010.

Карпов Ю.Г. Теория автоматов.-М.,2011.

Кнут Д. Искусство программирования. Тома 1, 2, 3.-М.,2001.

Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ.- М.,2008.

Лавриненко А.Е. Теория алгоритмов.-М.,2009.

Макконнел Дж. Анализ алгоритмов.-М.,2009.

Половов P.M. Теория автоматов.-М.,2007.

Романовский И.В. Дискретный анализ.-М.,2010.

Ульман Дж. Структуры данных и алгоритмы.-М.,2009.

Фалевич Б.Я. Теория алгоритмов.-М.,2009.

Фалина Н.М. Машина Тьюринга.-М.,2007.

¹ ФалевичБ.Я. Теория алгоритмов.-М..2009.-С.ЗЗ

² Макконел Дж. Анализ алгоритмов.- М., 2009. - с.90

³ Ульман Дж. Структуры данных и алгоритмы.-М.2009.-С. 182

⁴ Романовский И В. Дискретный анализ.-М.2010.-С.218