книги / Математическая логика и теория алгоритмов. Анализ алгоритмов

В строке 2 на каждой итерации выполняется 1 сравнение, количество операций в остальных строках определим как обычно (в строке 4 операцию целочисленного деления div тоже считаем как одну элементарную операцию).

Для начала рассмотрим строки 1, 9, 10, 11. Они выполняются всего 1 раз, причем в условном операторе в строке 9 сложность обеих ветвей равна 1. Таким образом, суммарная сложность этих строк будет следующей:

2 (строка 1) + 1 (строка 9) + 1 (строка 10 или 11) = 4.

Рассмотрим строки 2, 4–7. В силу наличия условного оператора в строке 5 нам придётся анализировать худший, средний и лучший случаи. Рассмотрим худший случай (каждый раз срабатывает ветка «then», сложность которой равна 2, что больше, чем сложность ветки «else», равной 1). Значит, на каждой итерации цикла while будут выполняться строки 2, 4, 5, 6, общая сложность которых равна 7. Самое сложное в этой задаче – определить, сколько раз выполнятся эти строки, то есть определить число повторений цикла Kповт.

Для этого придётся проанализировать суть представленного алгоритма. Рассмотрим величину r –l и обозначим через dk значение этой величины на k-й итерации цикла. Перед первой итерацией d0=n–1. Затем на каждой итерации цикла изменяется либо l, либо r,ирассматриваемаявеличинастановитсяравнойлибо

l r				2r l r 1		r l 1			d				,
dк r (mid 1) r			1								k 1
	2			2			2
										2

либо

dk mid l l 2r l l r2 2l r 2 l d2k 1 .

(mid – это среднее между l и r. Оно вычисляется в программе вот в этой строчке: mid:=(l+r) div 2;)

101

Таким образом, рассматриваемая величина каждый раз уменьшается примерно в 2 раза, пока не станет равна 0 (условие l<r равносильно тому, что d = r – l > 0). Пусть, например, n = 16,

тогда d0 = 15, d1 = 7, d2 = 3, d3 = 1, d4 = 0, то есть Kповт = 4. Если n = 32, то d0 = 31, d1 = 15, d2 = 7, d3 = 3, d4 = 1, d5 = 0, то есть

Kповт = 5. Несложно понять, что n и Kповт связаны формулой:

Kповт log2 n.

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

bin_find: tbinmax_ find (n) 4 Kповт 7 7 log2 n 4~O(log2 n).

Лучший случай отличается только тем, что вместо строки 6 будет выполняться строка 7, поэтому сложность тела цикла со-

ставит: 1+3+1+1=6.

В итоге получаем следующую нижнюю оценку сложности процедуры:

bin_find: tbinmin_ find (n) 4 Kповт 6 6 log2 n ~O(log2 n).

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

Ответ: tbin _ find (n) ~ O(log2 n).

Задачи для коллективного решения у доски

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

11. Для процедуры, выполняющей сортировку «простого выбора» одномерного массива размерности n, определить верхнюю, нижнюю и среднюю оценки сложности. Текст процедуры:

102

procedure sort2;

var i,j,min,t:integer; begin

for i:=1 to n-1 do begin

min:=i;

for j:=i+1 to n do

if M[j]<M[min] then min:=j; t:=M[min];

M[min]:=M[i];

M[i]:=t end

end;

12. Определить порядок роста функции сложности для процедуры сложения двух «длинных» чисел (числа, состоящие из n и m цифр соответственно, записаны в обратном порядке, по одному разряду в каждом элементе массива a[i] и b[i] соответственно). Текст процедуры приведен ниже:

procedure ADD;

var min,i,p,sum:integer; begin

if n<m then min:=n else min:=m; p:=0;

for i:=1 to min do begin

sum:=p+a[i]+b[i]; res[i]:=sum mod 10; p:= sum div 10

end;

if n<m then

for i:=min+1 to m do begin

sum:=p+b[i]; res[i]:=sum mod 10; p:=sum div 10

end else

for i:=min+1 to n do begin

sum:=p+a[i];

103

res[i]:=sum mod 10; p:=sum div 10

end;

if p>0 then

if n<m then res[m+1]:=p else res[n+1]:=p

end;

Задача для самостоятельной работы на занятии

13.Найтиверхнююинижнююоценкисложностиалгоритма:

function convert(s:string, n:integer):integer; var i, num : integer;

begin

i: = 1; num: = 0;

while (i <= n) and ((s[i]<'0') or (s[i] > '9')) do i:=i+1;

while (i <= n) and (s[i] >= '0') and (s[i] <= '9') do

begin

num: = num * 10 + s[i] - '0'; i:=i+1

end;

convert := num

end;

Задача для самостоятельной работы дома

14. Найти верхнюю, нижнюю и среднюю оценки сложности дляпроцедуры:

procedure up(s: string, n:integer) var i:integer;

begin

for i := 1 to n do

if (s[i]>='a') and (s[i] <= 'z') s[i] := s[i] + 'A' - 'a'

end;

Для вычисления средней оценки считать, что в среднем 3/4 символов строки являются малыми буквами.

104

ОТВЕТЫИСОВЕТЫ

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 1 АНАЛИЗ СЛОЖНОСТИ НЕРЕКУРСИВНЫХ АЛГОРИТМОВ

1.Существует несколько определений. В соответствии

сГОСТ 19.781–74 «Машины вычислительные. Программное обеспечение. Термины и определения» алгоритм – это точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату.

Другое возможное определение: алгоритм – точное предпи-

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

2.Алгоритм может быть описан неформально на естественном языке или псевдокоде. К формальным способам записи алгоритма относятся схемы алгоритмов, управляющие графы программ, записи на алгоритмическом языке или каком-либо языке программирования.

3.Основные свойства алгоритмов:

1)элементарность шагов

2)детерминированность

3)массовость

Иногда также выделяют свойства дискретности и конечности (результативности).

4.К основным характеристикам относятся объем оперативной памяти и время, необходимые для успешного завершения алгоритма. Наиболее важной характеристикой является именно время работы, которое называется также временной сложностью алгоритма.

5.Время работы алгоритма в общем случае зависит от входных данных. Для оценки временной сложности алгоритма все входные данные группируют по их объему (сложности) и рас-

105

X:V (X ) V

max

сматривают время работы алгоритма как функцию от объема входных данных.

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

6.Элементарная операция – это операция, время выполнения которой не зависит от объема обрабатываемых данных, то есть является константой на фиксированном устройстве. К элементарным операциям относятся арифметические и логические операции, операции сравнения и присваивания, выполняемые над данными стандартных скалярных типов.

7.Функция сложности алгоритма – это функция t (V), равная количеству элементарных операций, выполняемых алго-

ритмом при входных данных объема V.

8. Верхняя, нижняя и средняя оценки сложности – это оценки функции сложности алгоритма, которые используются в том случае, когда точная функция сложности t (V) не может быть найдена либо её поиск затруднителен. Такая ситуация возникает, если на входе алгоритма могут появиться входные данные, одинаковые по объему, но разные по значению, то есть такие X и Y, что V (X) = V (Y), но X Y (например, разные массивы одинаковой длины).

Верхняя оценка сложности tmax (V ) – это оценка «в худшем случае». Она показывает максимальное число элементарных операций, выполняемых алгоритмом при входных данных объема V, то есть tmax (V ) t (X ).

Нижняя оценка сложности tmin (V ) – это оценка «в луч-

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

объема V, то есть tmin (V )	min t (X ).
	X:V (X ) V

106

Средняя оценка сложности tсредн (V ) – это оценка «в среднем». Она показывает число элементарных операций, выполняемых алгоритмом при входных данных объема V с учётом вероятности появления тех или иных входных данных.

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

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

ОТВЕТЫ НА ЗАДАЧИ

10.Ответ зависит от конкретной реализации. В любом случае порядок роста должен получиться O (n).

11.Ответ:

tsort2max (n) n2 3n 4 ~ O(n2) ,

tsort2средн(n) 34n2 134 n 4 ~ O(n2),

tsortmin (n) 12n2 72n 4 ~ O(n2).

12. Ответ:

tADD (n,m) ~ O (n+m) или O (max (n,m)).

107

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 2 АНАЛИЗ СЛОЖНОСТИ РЕКУРСИВНЫХ АЛГОРИТМОВ

Цель занятия: научиться решать рекуррентные уравнения и анализировать сложность рекурсивных алгоритмов.

Контрольные вопросы

Прежде чем приступить к решению задач, ответьте на следующие вопросы:

1.Запишитеобщийвидлинейногорекуррентногоуравнения.

2.Какие уравнения называются уравнениями с постоянными коэффициентами?Какиеуравненияназываютсяоднородными?

3.Что значит решить рекуррентное уравнение?

4.Опишите алгоритм решения линейного однородного рекуррентногоуравненияспостояннымикоэффициентамиглубины2.

5.Опишите алгоритм решения линейного неоднородного рекуррентного уравнения с постоянными коэффициентами, в ко-

тором свободный член имеет следующий вид: f (n) Pk (n) qn , где Pk (n) – многочлен степени k.

6.Что такое рекурсивная процедура (функция)?

7.Приведите примеры рекурсивных алгоритмов.

8.Запишите общий вид рекуррентного уравнения для нахождения сложности рекурсивной процедуры (функции) для случая простой рекурсии.

Методика решения задач
Задача 1. Решить рекуррентное уравнение:
xn 1 5xn 16n, x0 3.	(1)

Решение. Данное уравнение является линейным рекуррентным уравнением с постоянными коэффициентами. Глубина

108

равна 1. Уравнение является неоднородным в силу наличия слагаемого «16n». Будем действовать в соответствии с алгоритмом решения неоднородных рекуррентных уравнений.

1.Составимоднородноеуравнение,отбросивнеоднородность: xn 1 5xn .

Составим характеристическое уравнение, заменив xn на n, получим:

n 1 5 n .

Разделив обе части уравнения на n ( 0), получим решение:

5.

Полученное решение позволяет записать общий вид решения однородного уравнения:

xо.о. C n C 5n.	(2)
n

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

xч.н. An B .	(3)
n

Неизвестные коэффициенты A, B найдём путём подстановки выражения (3) в исходное уравнение (1):

A n 1 B 5 An B 16n

An A B 5A 16 n 5B.

109

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

пенях n:
	4A 16	A 4,
A 5A 16
A B 5B	A 4B	B 1.

Подставим найденные коэффициенты в (3), получим
xч.н. 4n 1.	(4)
n

3. Составим общее решение неоднородного уравнения как сумму общего решения однородного (2) и частного решения неоднородного уравнения (4):

x	xо.н. xо.о. xч.н. C 5n 4n 1.			(5)
n	n	n	n

Наконец, для нахождения константы C подставим начальные условия, то есть подставим n = 0:

x0 C 50 4 0 1 C 1.

По условию x0 = 3, поэтому C + 1 = 3, откуда C = 2. Получаем окончательный ответ:

xn 2 5n 4n 1.

Выполним проверку, подставив найденное выражение в исходноеуравнение(1):

2 5n 1 4 (n 1) 1 5 (2 5n 4n 1) 16n, 10 5n 4n 4 1 10 5n 20n 5 16n, 10 5n 4n 5 10 5n 4n 5.

Получили тождественное равенство.

Начальноеусловиетожевыполняется:250+40+1= 2+1=3. Значит, уравнение решено верно.

110