Наиболее сложными частями программы обычно является выполнение цик-
лов и вызовов процедур. В предыдущем примере весь алгоритм выполнен с помо-
щью двух циклов.
Если одна процедура вызывает другую, то необходимо более тщательно оценить
сложность последней. Если в ней выполняется определенное число инструкций,
например, вывод на печать, то на оценку порядка сложности она практически не
влияет. С другой стороны, если в вызываемой процедуре выполняется O(N) ша-
гов, то функция может значительно усложнять алгоритм. Если процедура вызыва-
ется внутри цикла, то влияние может быть намного больше.
В качестве примера возьмем программу, содержащую медленную процедуру
Slow со сложностью порядка О(№) и быструю процедуру Fast со сложностью
порядка О(№). Сложность всей программы зависит от соотношения между этими
двумя процедурами.
Если при выполнении циклов процедуры Fast всякий раз вызывается проце-
дура Slow, то сложности процедур перемножаются. Общая сложность равна про-
изведению обеих сложностей. В данном случае сложность алгоритма составляет
O(N^2) * O(N^3) или О(№* N^2) = О(№). Приведем соответствующий фрагмент кода:
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
1 // Выполнение каких-либо действий.
end;
procedure Fast;
var
i, j : Integer;
begin
for i := 1 to N do
for j := 1 to N do
Slow; // Вызов процедуры Slow.
end;
procedure RunBoth;
begin
Fast;
end;
С другой стороны, если основная программа вызывает процедуры отдельно,
их вычислительная сложность складывается. В этом случае итоговая сложность
по порядку величины равна O(N^3) + O(N^2) = 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 RunBoth;
begin
Fast;
Slow;
end;
|
Главная
Каталог файлов
