29. Понятие сложности алгоритма и сложности (объема) входных данных. Основные правила вычисления сложности алгоритма (сложность линейного алгоритма, ветвления, цикла).

Способы оценки сложности:

1. Экспериментальные исследования.

Основные требования:

- множество разнообразных тестов с неповторяющимися закономерностями; - в наборе тестов должны присутствовать все «крайние» случаи;

- преимущество «обычных» входных данных.

Основные недостатки:

- сложность экстраполяции на другие объемы данных;

- занимает длительное время;

- результаты сильно зависят от конкретной реализации.

2. Теоретическая оценка.

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

На сложность алгоритма может влиять не только сама задача, но и ограничения на входные данные.

Понятие сложности алгоритмов:

1. Временная: оценивается

2. Емкостная: характеризует объем памяти, необходимый для хранения входных и выходных данных и промежуточных результатов.

x – входные данные

t_α(х) – функция сложности – оценка времени работы алгоритма на входных данных х.

Перейдем от х к характеристике входных данных v(x), которую будет называть объемом (сложностью) входных данных.

t_α(v) – сложность алгоритма

Пример:

function (n: integer): integer

var i,p: integer;

begin

p:=1; 1 оп

for i:=2 to n do p:=p*I n-1 разпо 2

f:=p; 1 оп

end;

итого: 1+(n-1)*2+1=2n операций

V(n) – значение числа n

t_α(v)=2n

Верхняя (нижняя) оценка сложности алгоритма (t_α(v)) – это функция, отражающая максимальное (минимальное) количество операций, выполняемое алгоритмом при поступлении на вход данных объемом V, т.е. это их оценка в худшем (лучшем) случае.

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

По умолчанию подразумевают среднюю оценку сложности. Ее сложнее всего получить.

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

Сложность алгоритма удобно оценивать по блок-схеме или ее упрощенному варианту – управляющему графу.

Линейные алгоритмы

Ветвление

М_А – количество данных, при котором алгоритм идет по ветке А.

Цикл

1) заранее известно количество повторений

2) заранее неизвестно количество повторений

Универсальных методов нет

Пример. Бинарный поиск в упорядоченном массиве

function bin_find (m:mas; n,x: integer): integer;

var l,r,mid: integer;

begin

l:=1; r:=n; 2 оп

while l<r do

begin

mid:=(l+r) div 2; 3 оп

if x>m[mid] then max 3 оп

l:=mid+1 min 2 оп

else r:=mid; mid 1/2*2+1/2*3=2,5 оп

end;

if m[l]=x then bin_find:=l 2 оп

else bin_find:=0;

end;