Для большинства задач существует много различных алгоритмов решения. Какой из них выбрать для решения конкретной задачи? Эффективность программы (кода) является очень важной ее характеристикой. В программировании всегда стараются выбирать наиболее эффективное решение и оценивать границы применимости выбранного алгоритма[1].
Рассмотрим пример 1 такой оценки. Некоторое агентство недвижимости имеет базу данных из n записей, причём каждая запись содержит одно предложение (что имеется) и один запрос (что требуется) относительно объектов недвижимости. Требуется подобрать варианты обмена – найти все такие пары записей, в которых предложение первой записи совпадает с запросом второй записи и наоборот. Допустим, что сравнение одной пары записей занимает одну миллисекунду. Тогда при поиске решения самым
простым способом («лобовой» алгоритм) – каждая запись сравнивается со всеми другими – потребуется n(n-1)/2 сравнений.
Если в базе данных n=100, то решение будет получено за 4,95 секунды. Но если n=100 000 (более реальный вариант), то время получения решения составит 4 999 950 секунд, 1389 часов, 58 суток, 2 месяца. Причём это оценка времени подбора прямых вариантов, а в реальной жизни число участников обмена чаще всего больше двух.
Этот пример показывает, что при выборе алгоритма для решения задачи необходимо оценить размер задачи (количество входных данных) и эффективность алгоритма, решающего эту задачу.
Эффективность алгоритма оценивается по двум параметрам: по времени работы и необходимому объёму памяти.
Сложность по памяти (пространственная/ёмкостная сложность)
алгоритма – количество памяти, необходимое для выполнения этого алгоритма, в зависимости от размера входных данных.
Компьютеры обладают ограниченным объемом памяти. Если две программы реализуют идентичные функции, то та, которая использует меньший объем памяти, будет более эффективна.
Вначале (70-80 годы) объём памяти являлся доминирующим фактором при выборе алгоритма. Затем, в связи с быстрым удешевлением памяти, эта оценка эффективности алгоритма постепенно теряла свое значение. Однако в настоящее время, в связи с широким распространением различных портативных устройств, выполняющих в том числе и функции компьютера, требования к объёму памяти снова являются актуальными.
Временная сложность алгоритма – зависимость числа операций, выполняемых алгоритмом, от размера входных данных.
Замечание: время работы одного и того же алгоритма в секундах (минутах и т.д.) может отличаться для компьютеров с разным быстродействием, поэтому для универсальной оценки используют количество операций в алгоритме.
При подсчёте учитываются только существенные операции – операции сравнения двух значений, сложения, вычитания, умножения, деления, MOD, DIV, вычисление значений булевских операций OR, NOT, AND.
Операции вычисления SIN, COS, EXP, LOG и т.д. оцениваются через число сложений и умножений, т.к. их вычисление для конкретных значений реализуется разложением в ряд.
Операции присваивания и операции со счётчиком при организации цикла не учитываются, т.к. их выполнение занимает значительно меньше времени, а их доля в общем числе операций падает при существенном росте размера задачи.
Для конкретного алгоритма вычисление точного вида функции временной сложности довольно трудоёмко, поэтому на практике вместо точных формул используют сравнительные оценки поведения функции сложности с увеличением размера входных данных.
Пусть N – размер входных данных алгоритма.
Тогда асимптотической сложностью алгоритма называется поведение функции сложности с ростом N.
Математически асимптотическая сложность вычисляется с помощью О-функций (будем использовать «О-большое»). O-функции выражают относительную скорость алгоритма в зависимости от некоторой переменной (или переменных).
Определение. Функция f(n) имеет порядок O(g(n)), если имеется константа К и счетчик n0, такие, что f(n) ≤ K*g(n), для n>n0.
Основные соотношения для О-функций:
1) O(k*f) = O(f), где k – некоторая константа
2) O(f*g) = O(f)*O(g) или O(f/g)=O(f)/O(g)
3) O(f+g) равна доминанте O(f) и O(g)
Например: 1,5*N=O(N),
О((17*N)*N) = O(17*N)*O(N) = O(N)*O(N)=O(N*N) = O(N²)
O(N5+N2)=O(N5).
Классы сложности
В теории алгоритмов классами сложности называются множества вычислительных задач, примерно одинаковых по сложности вычисления. Говоря более узко, классы сложности — это множества предикатов (функций, получающих на вход слово и возвращающих ответ 0 или 1), использующих для вычисления примерно одинаковые количества ресурсов[1].
Для каждого класса существует категория задач, которые являются «самыми сложными». Это означает, что любая задача из класса сводится к такой задаче, и притом сама задача лежит в классе. Такие задачи называют полными задачами для данного класса. Наиболее известными являются NP-полные задачи.
Каждый класс сложности (в узком смысле) определяется как множество предикатов, обладающих некоторыми свойствами. Типичное определение класса сложности выглядит так: классом сложности X называется множество предикатов P(x), вычислимых на машинах Тьюринга и использующих для вычисления O(f(n)) ресурса, где n — длина слова x.
В качестве ресурсов обычно берутся время вычисления (количество рабочих тактов машины Тьюринга) или рабочая зона (количество использованных ячеек на ленте во время работы). Языки, распознаваемые предикатами из некоторого класса (то есть множества слов, на которых предикат возвращает 1), также называются принадлежащими тому же классу. Кроме того, многие классы могут также быть описаны в терминах математической логики.
Все классы сложности находятся в иерархическом отношении: одни включают в себя другие. Однако про большинство включений неизвестно, являются ли они строгими. Одна из наиболее известных открытых проблем в этой области — равенство классов P и NP. Если это предположение верно (в чём большинство учёных сомневается), то представленная справа иерархия классов сильно свернётся. На данный момент наиболее распространённой является гипотеза о невырожденности иерархии (то есть все классы различны). Кроме того, известно, что EXPSPACE не равен классу PSPACE.
Рассмотрим функцию f и входную цепочку длиной n. Тогда класс DTIME(f(n)) определяют, как класс языков, принимаемых детерминированными машинами Тьюринга, заканчивающими свою работу за время, не превосходящее f(n). Класс NTIME(f(n)), в свою очередь, определяют, как класс языков, принимаемых недетерминированной машиной Тьюринга, заканчивающими свою работу за время, не превосходящее f(n). Отметим, что ограничения на память при определении данных классов отсутствуют.
Аналогично иерархии по времени вводится иерархия по памяти. Класс DSPACE(f(n)) обозначает класс языков, принимаемых детерминированными машинами Тьюринга, использующих не более f(n) ячеек памяти на рабочих лентах. Класс NSPACE(f(n)) определяют, как класс языков, принимаемых недетерминированными машинами Тьюринга, использующих не более f(n) ячеек памяти на рабочих лентах. Временные ограничения при определении данных классов отсутствуют.
Аналогично определяются и другие подобные рассмотренным выше классы. Приведем использующиеся сокращения:
D - детерминированный (детерминистический)
N - недетерминированный
R - вероятностный с ограниченной односторонней ошибкой
B - вероятностный с ограниченной двусторонней ошибкой
BQ - квантовый с ограниченной двусторонней ошибкой
О-сложность алгоритмов
O(1) Большинство операций в программе выполняются только раз или только несколько раз. Алгоритмами константной сложности. Любой алгоритм, всегда требующий независимо от размера данных одного и того же времени, имеет константную сложность[1].
О(N) Время работы программы линейно обычно когда каждый элемент входных данных требуется обработать лишь линейное число раз.
О(N2), О(N3), О(Nа) Полиномиальная сложность. О(N2)-квадратичная сложность, О(N3)- кубическая сложность.
О(Log(N)) Когда время работы программы логариф- мическое, программа начинает работать намного медленнее с увеличением N. Такое время работы встречается обычно в программах, которые делят большую проблему в маленькие и решают их по отдельности.
O(N*log(N)) Такое время работы имеют те алгоритмы, которые делят большую проблему в маленькие, а затем, решив их, соединяют их решения.
O(2N) Экспоненциальная сложность. Такие алгоритмы чаще всего возникают в результате подхода, именуемого метод грубой силы.
Программист должен уметь проводить анализ алгоритмов и определять их сложность. Временная сложность алгоритма может быть посчитана исходя из анализа его управляющих структур.
Алгоритмы без циклов и рекурсивных вызовов имеют константную сложность. Если нет рекурсии и циклов, все управляющие структуры могут быть сведены к структурам константной сложности. Следовательно, и весь алгоритм также характеризуется константной сложностью. Определение сложности алгоритма в основном сводится к анализу циклов и рекурсивных вызовов.
Например, рассмотрим алгоритм обработки элементов массива.
For i:=1 to N do
Begin
...
End;
Сложность этого алгоритма O(N), т.к. тело цикла выполняется N раз, и сложность тела цикла равна O(1).
Если один цикл вложен в другой и оба цикла зависят от размера одной и той же переменной, то вся конструкция характеризуется квадратичной сложностью.
For i:=1 to N do
For j:=1 to N do
Begin
...
End;
Сложность этой программы О(N2).
Давайте оценим сложность программы "Тройки Пифагора". Существуют два способа анализа сложности алгоритма: восходящий (от внутренних управляющих структур к внешним) и нисходящий (от внешних и внутренним).
O(H)=O(1)+O(1)+O(1)=O(1);
O(I)=O(N)*(O(F)+O(J))=O(N)*O(доминанты условия)=О(N);
O(G)=O(N)*(O(C)+O(I)+O(K))=O(N)*(O(1)+O(N)+O(1))=O(N2);
O(E)=O(N)*(O(B)+O(G)+O(L))=O(N)* O(N2)= O(N3);
O(D)=O(A)+O(E)=O(1)+ O(N3)= O(N3)
Сложность данного алгоритма O(N3).
Как правило, около 90% времени работы программы требует выполнение повторений и только 10% составляют непосредственно вычисления. Анализ сложности программ показывает, на какие фрагменты выпадают эти 90% -это циклы наибольшей глубины вложенности. Повторения могут быть организованы в виде вложенных циклов или вложенной рекурсии.
Эта информация может использоваться программистом для построения более эффективной программы следующим образом. Прежде всего можно попытаться сократить глубину вложенности повторений. Затем следует рассмотреть возможность сокращения количества операторов в циклах с наибольшей глубиной вложенности. Если 90% времени выполнения составляет выполнение внутренних циклов, то 30%-ное сокращение этих небольших секций приводит к 90%*30%=27%-му снижению времени выполнения всей программы.
Анализом эффективности алгоритмов занимается отдельный раздел математики и найти наиболее оптимальную функцию бывает не так - то и просто. Давайте оценим алгоритм бинарного поиска в массиве - дихотомию.
Суть алгоритма: идем к середине массива и ищем соответствие ключа значению срединного элемента. Если нам не удается найти соответствия, мы смотрим на относительный размер ключа и значение срединного элемента и затем перемещаемся в нижнюю или верхнюю половину списка. В этой половине снова ищем середину и опять сравниваем с ключом. Если не получается, снова делим на половину текущий интервал.
function search(low, high, key: integer): integer;
var
mid, data: integer;
begin
while low<=high do
begin
mid:=(low+high) div 2;
data:=a[mid];
if key=data then
search:=mid
else
if key < data then
high:=mid-1
else
low:=mid+1;
end;
search:=-1;
end;
Решение:
Первая итерация цикла имеет дело со всем списком. Каждая последующая итерация делит пополам размер подсписка. Так, размерами списка для алгоритма являются
n n/21 n/22 n/23 n/24... n/2m
В конце концов будет такое целое m, что
n/2m < 2 или n < 2m+1
Так как m - это первое целое, для которого n/2m <2, то должно быть верно
n/2m-1 > = 2 или 2m=< n
Из этого следует, что
2m = < n < 2m+1
Возьмем логарифм каждой части неравенства и получим
m=<log n=x<m+1
Значение m - это наибольшее целое, которое =<х.
Итак, O(log n).
Обычно решаемая задача имеет естественный "размер" (обычно количество данных ею обрабатываемых) которое мы называем N. В конечном итоге нам бы хотелось получить выражение для времени, необходимого программе для обработки данных размера N, как функцию от N. Обычно на интересует средний случай - ожидаемое время работы программы на "типичных" входных данных, и худший случай - ожидаемое время работы программы на самых плохих входных данных.
Некоторые алгоритмы хорошо изучены в том смысле, что известны точные математические формулы для среднего и худшего случаев. Такие формулы разрабатываются посредством тщательного изучения программ с целью нахождения времени работы в терминах математических характеристик, и затем производя их математический анализ.
Несколько важных причин такого рода анализа:
1. Программы, написанные на языке высокого уровня, транслируются в машинные коды, и понять сколько времени потребуется для выполнения того или иного оператора может быть трудно.
2. Многие программы очень чувствительны к входным данным, и их эффективность может очень сильно от них зависеть. Средний случай может оказаться математической фикцией, не связанной с теми данными на которых программа используется, а худший случай маловероятен.
Лучший, средний и худший случаи очень большое влияние играют в сортировке. Объем вычислений при сортировке
O-анализ сложности получил широкое распространение во многих практических приложениях. Тем не менее необходимо четко понимать его ограниченность.
К основным недостаткам подхода можно отнести следующие:
1) для сложных алгоритмов получение O-оценок, как правило, либо очень трудоемко, либо практически невозможно,
2) часто трудно определить сложность "в среднем",
3) O-оценки слишком грубые для отображения более тонких отличий алгоритмов,
4) O-анализ дает слишком мало информации (или вовсе ее не дает) для анализа поведения алгоритмов при обработке небольших объемов данных.
Определение сложности в O-обозначениях - далеко нетривиальная задача. В частности, эффективность двоичного поиска определяется не глубиной вложенности циклов, а способом выбора каждой очередной попытки.
Еще одна сложность - определение "среднего случая". Обычно сделать это достаточно трудно из-за невозможности предсказания условий работы алгоритма. Иногда алгоритм используется как фрагмент большой, сложной программы. Иногда эффективность работы аппаратуры и/или операционной системы, или некоторой компоненты компилятора существенно влияет на сложность алгоритма. Часто один и тот же алгоритм может использоваться в множестве различных приложений.
Из-за трудностей, связанных с проведением анализа временной сложности алгоритма "в среднем", часто приходится довольствоваться оценками для худшего и лучшего случаев. Эти оценки по сути определяют нижнюю и верхнюю границы сложности "в среднем". Собственно, если не удается провести анализ сложности алгоритма "в среднем", остается следовать одному из законов Мерфи, согласно которому оценка, полученная для наихудшего случая, может служить хорошей аппроксимацией сложности "в среднем".
Возможно, основным недостатком O-функций является их черезмерная грубость. Если алгоритм А выполняет некоторую задачу за 0.001*N с, в то время как для ее же решения с помощью алгоритма В требуется 1000*N с, то В в миллион раз быстрее, чем А. Тем не менее А и В имеют одну и ту же временную сложность O(N).
Большая часть данной лекции была посвящена анализу временной сложности алгоритмов. Существуют еще и другие формы сложности, о которых не следует забывать: пространственная и интеллектуальная сложность.
О пространственной сложности как объеме памяти, необходимой для выполнения программы, уже упоминалось ранее.
При анализе интеллектуальной сложности алгоритма исследуется понятность алгоритмов и сложность их разработки.
Все три формы сложности обычно взаимосвязаны. Как правило, при разработке алгоритма с хорошей временной оценкой сложности приходится жертвовать его пространственной и/или интеллектуальной сложностью. Например, алгоритм быстрой сортировки существенно быстрее, чем алгоритм сортировки выборками. Плата за увеличение скорости сортировки выражена в большем объеме необходимой для сортировки памяти. Необходимость дополнительной памяти для быстрой сортировки связана с многократными рекурсивными вызовами.
Алгоритм быстрой сортировки характеризуется также и большей интеллектуальной сложностью по сравнению с алгоритмом сортировки вставками. Если предложить сотне людей отсортировать последовательность объектов, то вероятнее всего, большинство из них используют алгоритм сортировки выборками. Маловероятно также, что кто-то из них воспользуется быстрой сортировкой. Причины большей интеллектуальной и пространственной сложности быстрой сортировки очевидны: алгоритм рекурсивный, его достаточно трудно описать, алгоритм длиннее (имеется в виду текст программы), чем более простые алгоритмы сортировки.