Вычислительная сложность алгоритмов сортировки 1 | Page 6

Если во внутренних циклах процедуры Fast происходит вызов процедуры Slow, то сложности процедур перемножаются. В данном случае сложность алгоритма составляет O(N^2 )*O(N^3 )=O(N^5).

Если же основная программа вызывает процедуры по очереди, то их сложности складываются: O(N^2 )+O(N^3 )=O(N^3). Следующий фрагмент имеет именно такую сложность:

procedure Slow;

var

i,j,k: integer;

begin

for i:=1 to N do

for j:=1 to N do

for k:=1 to N do

{какое-то действие}

end;

procedure Fast;

var

i,j: integer;

begin

for i:=1 to N do

for j:=1 to N do

{какое-то действие}

end;

procedure Both;

begin

Fast;

Slow;

end;