Вопрос 8: Алгоритмы: определение и свойства. Временная и пространственная сложность алгоритмов.

Под алгоритмом в самом широком смысле понимают точное и строгое описание последовательности операций, позволяющей за конечное число шагов получить решение задачи.

Свойства алгоритмов

            1. Дискретность: в начальный момент времени задается исходная конечная система величин, а в каждый следующий момент система величин получается по определенному закону (программе) из системы величин, имевшихся в предыдущий момент времени.

            2. Детерминированность: система величин, получаемых в какой-то (не начальный) момент времени, однозначно определяется системой величин, получаемых в предшествующие моменты времени.

            3. Элементарность шагов: закон получения последующей системы величин из предшествующей должен быть простым и локальным.

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

            5. Массовость: начальная система величин может выбираться из некоторого потенциально бесконечного множества.

            Понятие алгоритма, в какой-то мере определяемое требованиями 1-5, конечно, не строгое: в формулировках этих требований встречаются слова “способ”, “величина”, “простой”, “локальный”, точный смысл которых не установлен. Поэтому это нестрогое понятие алгоритма называется непосредственным или интуитивным определением алгоритма.

 

 Сложность алгоритмов

 

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

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

            Введем эти понятия сначала на простом примере. Пусть написана программа, определяющая для любого целого n>1 его наибольший делитель max_d, отличный от самого n (если n - простое, то результат - единица).

            Способ А решения поставленной задачи имеет вид:

                        ...

            i:=n-1;             while (n mod i <> 0) do i:=i-1;                      max_d:=i;

                        ...

            Цикл обязательно завершается, т.к. n mod 1 = 0.

            Способ Б решения этой же задачи основан на том, что разыскиваемый результат есть n/i, где i - наименьший делитель n, превосходящий единицу. Если n - простое, то i=n; в противном случае .

                        ...

            i:=2;     while (i<trunc(sqrt(n))) and (n mod i<>0) do           i:=i+1;

            if (n mod i = 0) then max_d:=n/i else max_d:=1;

                        ...

            Чтобы сравнить время выполнения алгоритмов А и Б, можно отметить, что оба они имеют вид:                        I1;        while (condition) do   I2;        I3;

            Пусть t1, t2, t3 - времена выполнения операторов I1, I2 и I3 соответственно. Предположим, что цикл while представлен в машине обычным образом с помощью одного условного и одного безусловного перехода, требующих соответственно времен tу и tб. Тогда время выполнения того и другого варианта определяется как      t= t1+t3+m(tу+t2+tб)+ tу,         (*)

где m - число повторений цикла. Введем обозначения P=t1+t3+tу;      Q=tу+t2+tб и подставим их в (*). Получим t=P+Qm.

            Рассмотрим “худший случай”: пусть входной параметр n - число простое. Тогда в способе А число выполнений цикла mА=n-2, в способе Б - mБ=-2.

            Для варианта А время выполнения алгоритма определяется в виде:

PА+QА(n-2)= QАn+(PА-2QА),

для варианта Б - в виде:

PБ+QБ(-2)= QБ+(PБ-2QБ).

            Детализация практической сложности ведет к вычислению постоянных PА, QА, PБ, QБ, определяемых конкретной ЭВМ и зависящих от времени выполнения ее команд. Более важна теоретическая сложность, сравнивающая два алгоритма. Когда n велико, QАn+(PА-2QА) ~ QАn, QБ+(PБ-2QБ) ~ QБ. Таким образом, в “худшем” случае временная сложность алгоритма А порядка n (обозначение: tА=O(n)), тогда как временная сложность алгоритма Б порядка  (tБ=O()).

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

            Максимальная сложность соответствует случаю, когда выбранные входные данные порождают наиболее долгое выполнение алгоритма. Именно о максимальной сложности шла речь в рассмотренном выше примере, т.к. при простом n оба алгоритма (и А, и Б) требуют наибольшего времени для своего выполнения.Средняя сложность соответствует случаю, когда алгоритм применяется к произвольным данным. Если же операция выполняется за фиксированное время, не зависящее от входных параметров, то считают, что она имеет сложность порядка единицы (O(1)).

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

            Представим теперь, что временная сложность некоторой задачи порядка 2n. Известно, что при n=10 задача решается за одну минуту. Увеличим n до 100. Время выполнения возрастет в 2100/ 210=290 раз. Учитывая, что 1 год состоит из 525600 минут, легко подсчитать, что задача будет решаться более чем 1020 лет, что существенно превышает всю историю человечества.

            Пусть для той же задачи удалось найти алгоритм с временной оценкой n5. В этом случае ситуация не столь безнадежна. При n=100 время решения задачи возрастет в 1005/105=105 раз, т.е. составит “всего лишь” два с небольшим месяца.

            Вообще, алгоритмы с полиномиальной оценкой (одна из них - n5) считаются приемлимыми, т.к. происходящий рост производительности ЭВМ заметно увеличивает и предельные размеры решаемых задач. Следует отметить, что уменьшение степени полинома в оценке хотя бы на 0.5 - это заметное достижение, т.к. оно заметно влияет на пределы применения алгоритма.