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

 

Алг(х)

if(условие)

then рекурсивная ветка

else тривиальная ветка

 

рекурсивная ветка – алг(y), где y=f(x)

вызов + доп. операции

Пусть t_α(x) –сложность алгоритма на входных данных x.

Пусть тривиальная ветка выполняется при входных данных s:

 

Пример:

n!=n(n-1)!

function F(n: integer): integer;

begin

if n>1

then F:=n* F(n-1)

else F:=1;

end;

;

s=1;

;

 

 

 

Ответ:

 

 

6. Решение рекуррентных соотношений вида T(n) = aT(n/d) + bn^k, T( 1 ) = C ₀ (без вывода). Сложность рекурсивного алгоритма быстрой сортировки.

 

, вместо перейдем к

Быстраясортировка

procedureQsort (m: mas; n, l, r: integer);

var mid, t, i, j: unteger;

begin

i:=l; j:=r;

mid:=m[(l+r) div 2];

while i<=j do

begin

while m[i]<mid

do i:=i+1;

while m[j]>mid

do j:=j-1;

if i<=j then

begin

t:=m[i];

m[i]:=m[j];

m[j]:=t;

i:=i+1; j:=j-1;

end;

end;

if j>l then Qsort(m,n,l,j);

if i<r then Qsort(m,n,i,r);

end;

-------------------------------------

1. нижняя оценка сложности