2. Количество повторений вложенного цикла зависит от параметра внешнего цикла

Введем следующие обозначения:

k - количество повторений внешнего цикла. В примере k=n.

f(k) – функция зависимости количества повторений вложенного цикла от числа повторений внешнего цикла. В примере f(1)=1, f(2)=2, … , f(n)=n.

T⁽¹⁾, T⁽²⁾ - временная сложность тела цикла 1-го (верхнего) уровня и 2-го уровня (вложенного цикла) соответственно. В примере T⁽²⁾ = 2.

a⁽¹⁾ - временная сложность операторов, предшествующих вложенному оператору цикла, в теле цикла верхнего уровня. В примере a⁽¹⁾ = 1.

b⁽¹⁾ - временная сложность операторов, следующих после вложенного оператора цикла, в теле цикла верхнего уровня. В примере b⁽¹⁾ = 2.

T – временная сложность всего алгоритма.

a – временная сложность операторов, предшествующих циклу, в основном алгоритме. В примере a=1.

b – временная сложность операторов, следующих после цикла в основном алгоритме. В примере b=1.

T = a+b+k∙( a⁽¹⁾ +b⁽¹⁾) + T⁽²⁾∙

11. Оценка сложности рекурсивных алгоритмов: рекурсия с одним и многими рекурсивными вызовами, случай косвенной рекурсии.

Под рекурсией понимается метод определения функции через её предыдущие и ранее определенные значения, а так же способ организации вычислений, при котором функция вызывает сама себя с другим аргументом.

При прямой рекурсии процедура содержит вызов себя в собственном теле, например:

procedure процедура_1

….

If … then процедура_1

….

end;

Косвенная рекурсия образуется цепочкой процедур, и эта цепочка замыкает себя в рекурсивное кольцо, например:

procedure процедура_1

….

… процедура_2

….

end;

procedure процедура_2

….

… процедура_3

….

end;

procedure процедура_3

….

… процедура_1

end;

• Для вычисления сложности рекурсивных алгоритмов используется рекуррентное уравнение:

T_a(X)=T_a(f(X))+ T_f(X)+ T_h(X)+ T_с(X,S)

T_a(S)=T_c(S,S)+ T_s(S)

Здесь

T_a(X) – общая сложность рекурсивного алгоритма

T_a(f(X)) – сложность предыдущего уровня рекурсии

T_f(X) – сложность вычисления аргументов при рекурсивном вызове процедуры

T_h(X) – сложность нерекурсивных вычислений

T_с(X,S) – сложность операции сравнения

T_s(S) – сложность вычисления нерекурсивного начального значения

T_c(S,S) – сложность операции сравнения для нерекурсивного начального значения

Пример:

Function F(n);

begin

If n=1 {проверка возможности прямого вычисления}

Then

F := 1

Else

F :=n*F(n-1); {рекурсивный вызов функции}

End;

X = n,

S = 1, n = 1

f(X)=n-1, FACTORIAL (n-1)

Tf(X)=1, FACTORIAL (n-1)

Th(X) = 2, FACTORIAL:= n * FACTORIAL (n-1)

Tc(X,S)=l, n = 1

Ts(S) = 1. FACTORIAL:= 1

Таким образом, система уравнений превращается в

Тa(n) = Тa(n-1)+4, Тa(1) = 2.

Ее решение – Тa(n) = 4n-2.

C НЕСКОЛЬКИМИ ВЫЗОВАМИ!

T_a(s)=k*T_a(f(X))+ k*T_f(X)+ T_h(X)+ T_с(X,S)

T_a(S)=T_c(S,S)+ T_s(S)

В случае косвенной рекурсии рекуррентное уравнение имеет вид: