СЛОЖНОСТЬ АЛГОРИТМОВ

ПОНЯТИЕ СЛОЖНОСТИ АЛГОРИТМА

Итак, алгоритм — точное предписание, задающее процесс преобразования исходных данных в результаты. Одним из древнейших является алгоритм Евклида для наибольшего общего делителя (НОД) двух натуральных (целых положительных, отличных от нуля) чисел. На современном языке это program NOD;

var Л, В, X, Y, NOD: cardinal:; begin X:=A; Y:=B; while Хф Y do

if X>Y then X:=X-Y else Y:= Y-X; NOD:= X;

end

Пусть выполнение цикла (рабочей части цикла) соответствует одному шагу алгоритма. Проследим его выполнение при А = 25, ? = 30.

Mi

X

Y

1

25

5

2

20

5

3

15

5

4

10

5

5

5

<5>

В правой нижней клетке таблице — результат, НОД = 5.

Введем дополнительное требование к алгоритму — эффективность. Все шаги алгоритма должны быть такими, чтобы пользователь мог выполнить их за конечное время, лежащее в некоторых разумных пределах, а если речь идет о вычислительной машине, то в пределах разумных ограничений используемой памяти.

С эффективностью алгоритма интуитивно связано понятие стоимости, понимаемой как оценка используемых ресурсов. Более точный смысл понятию стоимости позволяет придать понятие «сложность алгоритмов». Оно овеществляет стоимость во времени и пространстве, позволяет оценить время выполнения и объем требуемой памяти.

Сложность алгоритма оценивают по его динамическим характеристикам, а не по статическим: сложная программа может быстро выполняться, а простая — очень долго.

Практически сложность алгоритма связывают с основным его параметром, существенно влияющим на количество выполняемых действий. Как правило, это размер массива обрабатываемых данных (размер задачи).

Например, время работы алгоритма, выполняющего только операции чтения и занесения п данных в оперативную память, определяется формулой t = ап + Ь, где а — время чтения-записи, b — суммарное время вспомогательных операций. Здесь имеет место линейная зависимость от п, и сложность алгоритма называется линейной. Коэффициенты а и Ъ неизвестны, но зависят от ЭВМ, транслятора и т.д. Поэтому интересен характер зависимости от основного параметра; говорят о теоретической сложности, учитывая ту функцию от основного параметра, которая определяет сложность. В данном случае это О(п).

Сортировка с помощью прямого обмена («пузырьковая сортировка») п элементов списка представляет собой следующий процесс: определяется наименьший элемент всего списка и производится его обмен с первым элементом; затем определяется наименьший элемент оставшейся части списка и производится его обмен со вторым элементом и т.д. Значит, всего выполняется п — 1 сравнений при поиске первого элемента, п — 2 сравнений при поиске второго элемента и т.д.: (п — 1) + (п — 2) + ... + 1 = (п2 — п) / 2.

Это полином второй степени (говорят, что сложность алгоритма полиномиальна, а в данном случае — квадратична). Для больших п можно считать, что сложность 0(п2).

Если сложность алгоритма оценивается по уже написанной программе, то вместо числа сравнений вычисляется число внутренних циклов:

procedure СОРТИРОВКА;

<описание>; for к:= 1 to п— 1 do begin min:=A [А:]; for i:=k+1 to n do if min>A[i] then min:=Ai];

A[i]:=A[k]-

A[k]:=min;

end

Внешний цикл выполняется n — 1 раз. Внутренний цикл при каждом повторении внешнего срабатывает в среднем (при равномерном разбросе величин) п/2 раз. Умножив, получаем ту же самую величину.

При больших значениях п за асимптотическую оценку можно взять п2, т.е. сложность имеет порядок 0(п2).

Оценками времени работы алгоритма являются максимальное, минимальное и среднее время его выполнения. Они могут совпадать и не совпадать. В приведенной процедуре сортировки они совпадают, а в алгоритме Евклида не совпадают. Максимальное число шагов — циклов, очевидно, определяется ситуацией вида А = шах, В - 1. Тогда, если за параметр п взять значение А — В, то максимальная оценка сложности — порядка О(п). Но минимальная оценка сложности при А ф В соответствует ситуации А = 2В. Результат в этом случае достигается за один шаг, а сложность 0(1) не зависит от п.

«Усовершенствуем» алгоритм Евклида, прекращая его выполнение в том случае, если оказывается, что одно из чисел делится на другое. Тогда это и есть НОД: program NOD begin Х:=А; Y:=B; while X modYФ 0 or YmodXФ 0 do if X>Y then X:=X-Y else Y:=Y-X;

NOD:=min(X, Y) end

В примере вместо пяти выполнится один шаг, а в случае равенства одного из двух исходных чисел единице, так же как и в случае кратности одного числа другому, преобразования вообще не производятся.

Тем не менее — скорее интуитивно — следует считать среднее значение оценки сложности линейно зависящим от А — В, хотя достаточно низкий коэффициент можно установить статистически.

Также можно улучшить и алгоритм сортировки, о чем будет сказано далее.

Однако в большом числе задач верхние и нижние оценки совпадают на уровне порядка. Например, оценим сложность алгоритма умножения матриц размера п: for /:= 1 to п do for j:= to n do begin C[i,j]:=0;

for k:= 1 to n do C[i,j:=C[i,j+A[i, k]xB[k,j] end

Очевидно, что время срабатывания внутреннего цикла пропорционально л3. Как бы мы ни совершенствовали алгоритм, объективно существует число операций для решения задачи, такое, что верхние и нижние оценки сложности совпадают: 0(пу) = о(пг). В целом эта оценка также полиномиальная.

Итак, рассмотрим некоторый алгоритм А. Почти всегда существует параметр л, характеризующий объем его данных. Пусть функция Т(п) — время выполнения/!. Пусть/— некоторая функция от л. Говорят, что алгоритм А имеет теоретическую (асимптотическую) сложность Oif (л)), если

где к — положительное число.

Если алгоритм выполняется за фиксированное время, не зависящее от размера задачи, говорят, что его сложность равна 0(1). Это определение обобщается в случае, если время выполнения существенно зависит от нескольких параметров. Например, алгоритм, определяющий, входит ли множество т элементов в множество п элементов, может иметь в зависимости от используемых структур данных сложность 0(т х п) или 0(т + п).

Практически время выполнения алгоритма может зависеть от значений данных, как мы видели выше. Например, время выполнения некоторых алгоритмов сортировки существенно сокращается, если первоначально эти данные частично упорядочены. Чтобы учитывать это, сохраняя возможность анализировать алгоритм независимо от их данных, различают:

  • максимальную сложность, определяемую значением Ттах(п) — время выполнения алгоритма, когда выбранный набор п данных порождает наиболее долгое время выполнения алгоритма;
  • среднюю сложность, определяемую значением Тср(п) — средним временем выполнения алгоритма, примененного к п произвольным данным.

Эти понятия без труда распространяются на измерение стоимости в единицах объема памяти: можно говорить о средней и максимальной пространственной сложности. Вместе с тем технический прогресс привел к неактуальности рассмотрения ресурсов памяти. Поэтому на данном вопросе мы останавливаться не будем.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >