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

 

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

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

Ветвление

tB

tA

A

B

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

Цикл

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

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

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

 

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

functionbin_find (m:mas; n,x: integer): integer;

varl,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 оп

elsebin_find:=0;

end;