O(1) - Большинство операций в программе выполняются только раз или только несколько раз. Алгоритмами константной сложности. Любой алгоритм, всегда требующий независимо от размера данных одного и того же времени, имеет константную сложность.
О(N) - Время работы программы линейно обычно когда каждый элемент входных данных требуется обработать лишь линейное число раз.
О(N 2), О(N 3), О(N а) - Полиномиальная сложность.
О(N 2)-квадратичная сложность, О(N 3)- кубическая сложность
О(Log(N)) - Когда время работы программы логарифмическое , программа начинает работать намного медленнее с увеличением N. Такое время работы встречается обычно в программах, которые делят большую проблему в маленькие и решают их по отдельности.
O(N*log(N)) - Такое время работы имеют те алгоритмы, которые делят большую проблему в маленькие , а затем, решив их, соединяют их решения.
O(2 N) = Экспоненциальная сложность. Такие алгоритмы чаще всего возникают в результате подхода именуемого метод грубой силы.
Программист должен уметь проводить анализ алгоритмов и определять их сложность. Временная сложность алгоритма может быть посчитана исходя из анализа его управляющих структур.
Алгоритмы без циклов и рекурсивных вызовов имеют константную сложность. Если нет рекурсии и циклов, все управляющие структуры могут быть сведены к структурам константной сложности. Следовательно, и весь алгоритм также характеризуется константной сложностью.
Определение сложности алгоритма в основном сводится к анализу циклов и рекурсивных вызовов.
Например, рассмотрим алгоритм обработки элементов массива.
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;
Сложность этой программы О(N 2).
Существуют два способа анализа сложности алгоритма: восходящий (от внутренних управляющих структур к внешним) и нисходящий (от внешних и внутренним).
 |
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(N 2);
O(E)=O(N)*(O(B)+O(G)+O(L))=O(N)* O(N 2)= O(N 3);
O(D)=O(A)+O(E)=O(1)+ O(N 3)= O(N 3)
Сложность данного алгоритма O(N 3).
Как правило, около 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;
if key=data then
search:=mid
else
if key < data then
high:=mid-1
else
low:=mid+1;
end;
search:=-1;
end;
Первая итерация цикла имеет дело со всем списком. Каждая последующая итерация делит пополам размер подсписка. Так, размерами списка для алгоритма являются
n n/2 1 n/2 2 n/2 3 n/2 4 ... n/2 m
В конце концов будет такое целое m, что
n/2 m <2 или n<2 m+1
Так как m - это первое целое, для которого n/2 m <2, то должно быть верно
n/2 m-1 >=2 или 2 m = Из этого следует, что Обычно решаемая задача имеет естественный "размер" (обычно количество данных ею обрабатываемых) которое мы называем N. В конечном итоге нам бы хотелось получить выражение для времени, необходимого программе для обработки данных размера N, как функцию от N. Обычно на интересует средний случай - ожидаемое время работы программы на "типичных" входных данных, и худший случай - ожидаемое время работы программы на самых плохих входных данных. Некоторые алгоритмы хорошо изучены в том смысле, что известны точные математические формулы для среднего и худшего случаев. Такие формулы разрабатываются посредством тщательного изучения программ с целью нахождения времени работы в терминах математических характеристик, и затем производя их математический анализ. Несколько важных причин такого рода анализа: Лучший, средний и худший случаи очень большое влияние играют в сортировке. O-анализ сложности получил широкое распространение во многих практических приложениях. Тем не менее необходимо четко понимать его ограниченность. К основным недостаткам подхода
можно отнести следующие: Определение сложности в O-обозначениях - далеко нетривиальная задача. В частности, эффективность двоичного поиска определяется не глубиной вложенности циклов, а способом выбора каждой очередной попытки. Еще одна сложность - определение "среднего случая". Обычно сделать это достаточно трудно из-за невозможности предсказания условий работы алгоритма. Иногда алгоритм используется как фрагмент большой, сложной программы. Иногда эффективность работы аппаратуры и/или операционной системы, или некоторой компоненты компилятора существенно влияет на сложность алгоритма. Часто один и тот же алгоритм может использоваться в множестве различных приложений. Из-за трудностей, связанных с проведением анализа временной сложности алгоритма "в среднем", часто приходится довольствоваться оценками для худшего и лучшего случаев. Эти оценки по сути определяют нижнюю и верхнюю границы сложности "в среднем". Собственно, если не удается провести анализ сложности алгоритма "в среднем", остается следовать одному из законов Мерфи, согласно которому оценка, полученная для наихудшего случая, может служить хорошей аппроксимацией сложности "в среднем". Возможно, основным недостатком O-функций является их черезмерная грубость. Если алгоритм А выполняет некоторую задачу за 0.001*N с, в то время как для ее же решения с помощью алгоритма В требуется 1000*N с, то В в миллион раз быстрее, чем А. Тем не менее А и В имеют одну и ту же временную сложность O(N). Большая часть данной лекции была посвящена анализу временной сложности алгоритмов. Существуют еще и другие формы сложности, о которых не следует забывать: пространственная и интеллектуальная сложность. О пространственной сложности как объеме памяти, необходимой для выполнения программы, уже упоминалось ранее. При анализе интеллектуальной сложности алгоритма исследуется понятность алгоритмов и сложность их разработки. Все три формы сложности обычно взаимосвязаны. Как правило, при разработке алгоритма с хорошей временной оценкой сложности приходится жертвовать его пространственной и/или интеллектуальной сложностью. Например, алгоритм быстрой сортировки существенно быстрее, чем алгоритм сортировки выборками. Плата за увеличение скорости сортировки выражена в большем объеме необходимой для сортировки памяти. Необходимость дополнительной памяти для быстрой сортировки связана с многократными рекурсивными вызовами. Алгоритм быстрой сортировки характеризуется также и большей интеллектуальной сложностью по сравнению с алгоритмом сортировки вставками. Если предложить сотне людей отсортировать последовательность объектов, то вероятнее всего, большинство из них используют алгоритм сортировки выборками. Маловероятно также, что кто-то из них воспользуется быстрой сортировкой. Причины большей интеллектуальной и пространственной сложности быстрой сортировки очевидны: алгоритм рекурсивный, его достаточно трудно описать, алгоритм длиннее (имеется в виду текст программы), чем более простые алгоритмы сортировки. Для сравнения алгоритмов принято использовать обобщенную характеристику, называемую эффективностью. Говорят, что алгоритм Л, эффективнее
алгоритма А 2 ,
если алгоритм Л, выполняется за меньшее время и (или) требует меньше компьютерных ресурсов (оперативной памяти, дискового пространства, сетевого трафика и т.п.). Эффективный алгоритм должен удовлетворять требованиям приемлемого времени исполнения и разумной ресурсоемкое™, о чем уже упоминалось в параграфе 1.1. Совокупность этих характеристик составляет понятие сложности алгоритма. При увеличении времени исполнения алгоритма и (или) задействованных ресурсов сложность возрастает. Таким образом, понятия эффективности и сложности являются обратными один относительно другого. Характеристика алгоритма, отражающая временные затраты на его реализацию, называется временной сложностью.
Характеристика алгоритма, отражающая компьютерные ресурсные затраты на его реализацию, называется емкостной сложностью.
При количественной и качественной оценках алгоритма, связанных с определением сложности, используют два подхода - практический и теоретический. Практический подход
связан с реально выполняемыми алгоритмами на конкретных физических устройствах. Он характеризуется параметрами, которые можно измерить и зафиксировать. Временная сложность при таком подходе может выражаться во временных единицах (например, миллисекундах) или количестве тактов процессора, затрачиваемых на выполнение алгоритма. Емкостная сложность может выражается в битах (или других единицах измерения информации), минимальных аппаратных требованиях, необходимых для выполнения алгоритма, и пр. Практическая оценка не является абсолютным показателем эффективности алгоритма. Количественные значения, получаемые при таком подходе, зависят от множества факторов, таких как: Таким образом, алгоритм, выполняемый в одной и той же вычислительной системе для одних и тех же входных данных, может иметь различные количественные оценки в различные моменты времени. Поэтому более важным оказывается теоретический подход к определению сложности. Теоретическая сложность
характеризует алгоритм без привязки к конкретному оборудованию, программному обеспечению и средствам реализации. В этом случае временная сложность выражается в количестве операций, тактах работы машины Тьюринга и т.д. Емкостная сложность определяется объемом данных (входных, промежуточных, выходных), числом задействованных ячеек на ленте машины Тыоринга и т.д. При теоретическом подходе к оценке эффективности считается, что алгоритм выполняется на некотором идеализированном компьютере
, для которого время выполнения каждого вида операций известно и постоянно. Также считается, что ресурсы такого компьютера бесконечны, поэтому емкостную сложность при теоретическом подходе обычно не определяют. В качестве временной характеристики сложности выбирают количество инструкций (операций), выполняемых на идеализированном компьютере. Количественные оценки, получаемые при теоретическом подходе, также могут зависеть от ряда следующих факторов: Время выполнения алгоритма обычно зависит от объема входных данных (размер входа), под которым понимают размерность решаемой задачи. Так, при сортировке множества значений объем данных составляет количество элементов этого множества. При обработке строк объемом входных данных считается длина строки. Пусть п -
объем входных данных для некоторого алгоритма. Обозначим за Т(п)
количество инструкций, выполняемых на идеализированном компьютере при исполнении алгоритма, причем оно определяется для «наихудшего случая», когда объем операций максимален. Понятие «наихудшего случая» можно проиллюстрировать на примере. Пусть рассматривается алгоритм проверки наличия числового элемента в некотором множестве (массиве) чисел. Если это множество упорядочено по возрастанию, то, вообще говоря, нет смысла проверять элементы, расположенные после первого элемента, который больше искомого. В этом случае Т(п)
п. Однако в наихудшем случае (для произвольного несортированного множества) придется просмотреть все элементы множества. Очевидно, здесь Т(п) = п.
Вообще говоря, Т(п)
является некоторой функцией от объема входных данных п.
Во многих случаях Т(п)
выражается полиномиальной, степенной или логарифмической функцией от п.
Поведение величины Т(п)
в зависимости от увеличения п
называют асимптотической сложностью
алгоритма. Говорят, что Т(п
) имеет порядок сложности 0(J(n))
(читается «О
большое от/от п»)
для некоторого алгоритма, если существуют константа с
и объем данных щ
такие, что Уп > п 0
и имеет место неравенство Т(п
) с/(п). Данный факт записывается как Т(п) = 0(J(n))
и означает, что для функции Т(п)
существуют такая функция f(n)
и константа с, для которых, начиная с некоторого п 0 ,
значение Т(п)
не превосходит cf(n).
Функция f(n)
представляет собой верхнюю границу значений функции Т(п).
Пусть, например, Т(п) =
2п А
+ п 2 .
Выбрав значения п 0
= 0 и с =
5, для любого п > п 0
имеем Т(п) =
2п А
+ п 2
Т(п) имеет порядок я 4 . Функция Т(п
) связана с определенным алгоритмом, поэтому часто говорят, что порядок сложности 0(/(п))
имеет именно алгоритм. Говорят, что Т(п)
имеет нижнюю границу Q(g(n))
(читается «омега большое от g
от /г»), если существуют константа с и объем данных п 0
такие, что /п
и имеет место неравенство Т(п) > cg(n).
Данный факт записывается как Т(п) = Q(g(n)).
Пусть, например, Т(п) =
2я 4 + п 2 .
Выбрав значение с =
1, для любого п
имеем Т{п)
= 2я 4 + п 2 > сп А >
следовательно, Т(п
) имеет нижнюю границу я 4 . Нетрудно видеть, что порядок и нижняя граница не являются единственными для некоторой функции Т(п).
В примерах выше в качестве /(я) можно было выбрать я 5 , я 6 ,..., а в качестве g(n) -
я 3 , я 2 ,.... Обычно в качестве /(я) выбирают функцию с минимальной степенью, а в качестве g(n)
- с максимальной. Порядок сложности 0(/(я)) и нижняя граница Q(g(rc)) представляют собой классы функций. Интуитивно Q(g"(n)) можно понимать как класс функций растущих по крайней мере так же быстро, как и Т(п).
Аналогично, интуитивно 0(f(n))
можно понимать как класс функций, растущих не быстрее, чем Т(п). С
практической точки зрения при оценке сложности алгоритма наиболее важным оказывается именно класс функций 0(f(n)).
Определение вида функции /(я) и является основной задачей расчета
теоретической сложности алгоритма. Для любого алгоритма при определении степени роста можно воспользоваться следующими свойствами 0(/(я)): 1) 0(kf(ji))
= 0(/(я)), где k
= const. Таким образом, постоянный множитель в функции не оказывает влияние на скорость роста. Например, 2) 0(J(ri)"g(n)) = 0(J(n))"0(g(ri)).
Таким образом, порядок произведения двух функций равен произведению их сложностей. Например, Иногда это свойство записывают как 3) 0(/(п)
+ g(n))
равен доминанте
(функции с максимальной степенью) функций /(я) и g(n).
Например, В теории сложности алгоритмов выделяют следующие классы функций сложности: При увеличении размера входа сложность каждого последующего типа функций растет быстрее, чем предыдущего (кроме 0(log 2 /?)). Для достаточно большого объема входных данных предпочтительнее использовать алгоритмы с меньшей сложностью. При количественном подсчете сложности первоначально выбирают операцию или группу операций, которая значима для этого алгоритма (составляет его основу). В их качестве обычно выступают операции сравнения и арифметические операции. К операциям сравнения относят проверку значений двух величин (меньше, больше, равно, меньше или равно, больше или равно, не равно). Они считаются эквивалентными по времени выполнения. Арифметические операции, в свою очередь, делят на аддитивные
и мультипликативные.
К первым (часто называемым просто сложением)
относят сложение, вычитание, уменьшение или уменьшение значения счетчика. Ко вторым (называемым просто умножением)
относят умножение, деление, взятие остатка по модулю. Операции сложения выполняются быстрее, чем операции умножения, поэтому алгоритмы с меньшим количеством умножений являются предпочтительными, даже если количество сложений растет пропорционально количеству уменьшения умножений. Операции целочисленного умножения или деления па степень числа 2 относят к аддитивным операциям, так как при работе с ячейками памяти они сводятся к сдвигу, который эквивалентен операции сложения. После выбора значимых операций они делятся на две категории: Непосредственный подсчет или оценка количества выполняемых операций позволяет оценить Т(п).
Для оценки порядка сложности можно использовать анализ программного кода, реализующего алгоритм. При этом: Пример 1.3
Определить порядок сложности алгоритма программы на языке Pascal, приведенного в листинге 1.2. Строки программы пронумерованы в виде комментариев (см. параграф 2.6). Листинг 1.2
{01} for i:=l to n do
{02} begin
{03} write("Введите элемент массива
с индексом ",i,": ");
{04} Readln(MyArray[i]);
{05} end;
{06} for i:=l to n do
{07} for j:=1 to n do
{08} begin
{09} write("Введите элемент массива
с индексами ", i, ",", j, " : ");
{10} Readln(МуDArray);
{11} end;
Решение
Строки 02, 05, 08, 11 не содержат исполняемых операторов, поэтому при определении порядка они не учитываются. Строки 03 и 04 имеют порядок 0(1). Последовательное их выполнение имеет порядок 0(1) + 0(1) = 0(1). Аналогично, последовательное выполнение строк 09 и 10 имеет сложность 0(1). Цикл в строках 01-05 имеет сложность порядка О(п),
вложенные циклы в строках 06-11 - порядка 0(п 2).
Итоговая сложность алгоритма имеет порядок Оценка сложности алгоритма, как временной, так и ресурсной, позволяет определить максимальное и среднее время исполнения алгоритма. Это крайне важно при обработке больших массивов информации, особенно в задачах сортировки и поиска, рассмотренных далее. Если для решения задачи существует один алгоритм, то можно придумать и много других алгоритмов для решения этой же задачи. Какой алгоритм лучше подходит для решения конкретной задачи? По каким критериям следует выбирать алгоритм из множества возможных? Как правило, мы высказываем суждение об алгоритме на основе его оценки исполнителем-человеком. Алгоритм кажется нам сложным, если даже после внимательного его изучения мы не можем понять, что же он делает. Мы можем назвать алгоритм сложным и запутанным из-за того, что он обладает разветвленной логической структурой, содержащей много проверок условий и переходов. Однако для компьютера выполнение программы, реализующей такой алгоритм, не составит труда, так как он выполняет одну команду за другой, и для компьютера неважно - операция ли это умножения или проверка условия. Более того, мы можем написать громоздкий алгоритм, в котором выписаны подряд повторяющиеся действия (без использования циклической структуры). Однако с точки зрения компьютерной реализации такого алгоритма практически нет никакой разницы, использован ли в программе оператор цикла (например, 10 раз на экран выводится слово "Привет") или 10 раз последовательно выписаны операторы вывода на экран слова "Привет". Для оценки эффективности алгоритмов введено понятие сложности алгоритма.
Определение. Вычислительным процессом,
порожденным алгоритмом, называется последовательность шагов алгоритма, пройденных при исполнении этого алгоритма. Определение. Сложность алгоритма
- количество элементарных шагов в вычислительном процессе этого алгоритма. Обратите внимание, именно в вычислительном процессе, а не в самом алгоритме. Очевидно, для сравнения сложности разных алгоритмов необходимо, чтобы сложность подсчитывалась в одних и тех же элементарных действиях. Определение. Временная сложность алгоритма
- это время Т, необходимое для его выполнения. Оно равно произведению числа элементарных действий на среднее время выполнения одного действия: Т = kt.
Поскольку t
зависит от исполнителя, реализующего алгоритм, то естественно считать, что сложность алгоритма в первую очередь зависит от k.
Очевидно, что в наибольшей степени количество операций при выполнении алгоритма зависит от количества обрабатываемых данных. Действительно, для упорядочивания по алфавиту списка из 100 фамилий требуется существенно меньше операций, чем для упорядочивания списка из 100 000 фамилий. Поэтому сложность алгоритма выражают в виде функции от объема входных данных. Пусть есть алгоритм А. Для него существует параметр а,
характеризующий объем обрабатываемых алгоритмом данных, этот параметр часто называют размерностью задачи.
Обозначим через Т(n)
время выполнения алгоритма, через f
- некую функцию от п.
Определение.
Будем говорить, что Т(n)
алгоритма имеет порядок роста f(n), или,
по-другому, алгоритм имеет теоретическую сложность
O * (f(n))
,
если найдутся такие константы с 1 , с 2
> 0 и число п 0 ,
что c 1 f(n))
< Т(п) < c 2 f(n)
при всех п >= n 0 .
Здесь предполагается, что функция f(n)
неотрицательна, но крайней мере при п >= n 0 .
Если для Т(п)
выполняется условие Т(n) <= сf(п),
то говорят, что алгоритм имеет теоретическую сложность О(п)
(читается "о" большое от n). Так, например, алгоритм, выполняющий только операции чтения данных и занесения их в оперативную память, имеет линейную
сложность 0(п).
Алгоритм сортировки методом прямого выбора имеет квадратичную
сложность 0(п 2) ,
так как при сортировке любого массива надо выполнить (п 2 - п)/2
операций сравнения (при этом операций перестановок вообще может не быть, например, на упорядоченном массиве, в худшем случае надо будет выполнить п
перестановок). А сложность алгоритма умножения матриц
(таблиц) размера п
x п
будет уже кубической
O(n 3) , так как для вычисления каждого элемента результирующей матрицы требуется п
умножений и п - 1
сложений, а всего этих элементов п 2 .
Для решения задачи могут быть разработаны алгоритмы любой сложности. Логично воспользоваться лучшим среди них, т.е. имеющим наименьшую сложность. Наряду со сложностью важной характеристикой алгоритма является эффективность.
Под эффективностью понимается выполнение следующего требования: не только весь алгоритм, но и каждый шаг его должны быть такими, чтобы исполнитель был способен выполнить их за конечное разумное время. Например, если алгоритм, выдающий прогноз погоды на ближайшие сутки, будет выполняться неделю, то такой алгоритм просто-напросто никому не нужен, даже если его сложность будет минимальной для класса подобных задач. Если мы рассматриваем алгоритмы, реализующиеся на компьютере, то к требованию выполнения за разумное время прибавляется требование выполнения в ограниченном объеме оперативной памяти. Известно, что во многих языках программирования нет операции возведения в степень, следовательно, такой алгоритм надо программисту писать самостоятельно. Операция возведения в степень реализуется через операции умножения; с ростом показателя степени растет количество операций умножения, которые выполняются достаточно долго. Следовательно, актуален вопрос о создании эффективного алгоритма возведения в степень. Рассмотрим метод быстрого вычисления натуральной степени вещественного числа х.
Этот метод был описан еще до нашей эры в Древней Индии. Запишем п
в двоичной системе счисления. Заменим в этой записи каждую " 1" парой букв КХ,
а каждый "О" - буквой К. Вычеркнем крайнюю левую пару КХ. Полученная строка, читаемая слева направо, дает правило быстрого вычисления х n ,
если букву К
рассматривать как операцию возведения результата в квадрат, а букву X
- как операцию умножения результата на х.
Вначале результат равен х.
Пример 1. Возвести х в степень п = 100. Переведем число п в двоичную систему счисления: п = 100 10 = 1100100, Строим последовательность КХКХКККХКК Вычеркиваем АХ слева => КХКККХКК Вычисляем искомое значение К => возводим х в квадрат => получаем х 2 , X => умножаем результат на х=> получаем х 3 К => возводим результат в квадрат => получаем х 6 К=> возводим результат в квадрат => получаем х 12 , К=> возводим результат в квадрат => получаем х 24 , Х=> умножаем результат на х =>получаем х 25 К=> возводим результат в квадрат => получаем x 50 К=> возводим результат в квадрат => получаем х 100 . Таким образом, мы вычислили сотую степень числах всего за 8 умножений. Этот метод достаточно эффективный, так как он не требует дополнительной оперативной памяти для хранения промежуточных результатов. Однако заметим, что этот метод не всегда самый быстрый. Например, при п = 49 учащиеся могут предложить такой эффективный алгоритм возведения в степень: При реализации этого алгоритма было выполнено 7 операций умножения (вместо 48 операций при вычислении "в лоб") и использовано 3 ячейки (для хранения переменной х
, для хранения значения х 16
и для хранения текущего результата, получаемого на каждом шаге). Если же использовать алгоритм "Быстрого возведения в степень", то получим то же количество операций (7 операций умножения), но для реализации этого алгоритма потребуется только 2 ячейки (для хранения переменной х
и для хранения текущего результата). Сама операция умножения реализуется в процессоре не "в лоб", а опять же через эффективные рекурсивные алгоритмы. Об одном из таких алгоритмов вы можете прочитать в Хрестоматии. Мы же рассмотрим алгоритм "быстрого" умножения, который был известен еще в Древнем Египте, его также называют "русским", или "крестьянским", методом. Разберем пример применения этого алгоритма. Пример 2. Умножим 23 на 43 "русским" методом. Ответ: 23 х 43 = 23 + 46 + 184 + 736 = 989. В итоговую сумму вошли числа первого столбца, рядом с которыми во втором столбце стоят нечетные числа. Традиционно принято оценивать степень сложности алгоритма по объему используемых им основных ресурсов компьютера: процессорного времени и оперативной памяти. В связи с этим вводятся такие понятия, как временная сложность алгоритма и объемная сложность алгоритма. Параметр временной сложности становится особенно важным для задач, предусматривающих интерактивный режим работы программы, или для задач управления в режиме реального времени. Часто программисту, составляющему программу управления каким-нибудь техническим устройством, приходится искать компромисс между точностью вычислений и временем работы программы. Как правило, повышение точности ведет к увеличению времени. Объемная сложность программы становится критической, когда объем обрабатываемых данных оказывается на пределе объема оперативной памяти ЭВМ. На современных компьютерах острота этой проблемы снижается благодаря как росту объема ОЗУ, так и эффективному использованию многоуровневой системы запоминающих устройств. Программе оказывается доступной очень большая, практически неограниченная область памяти (виртуальная память). Недостаток основной памяти приводит лишь к некоторому замедлению работы из-за обменов с диском. Используются приемы, позволяющие минимизировать потери времени при таком обмене. Это использование кэш-памяти и аппаратного просмотра команд программы на требуемое число ходов вперед, что позволяет заблаговременно переносить с диска в основную память нужные значения. Исходя из сказанного можно заключить, что минимизация емкостной сложности не является первоочередной задачей. Поэтому в дальнейшем мы будем интересоваться в основном временной сложностью алгоритмов. Время выполнения программы пропорционально числу исполняемых операций. Разумеется, в размерных единицах времени (секундах) оно зависит еще и от скорости работы процессора (тактовой частоты). Для того чтобы показатель временной сложности алгоритма был инвариантен относительно технических характеристик компьютера, его измеряют в относительных единицах. Обычно временная сложность оценивается числом выполняемых операций. Как правило, временная сложность алгоритма зависит от исходных данных. Это может быть зависимость как от величины исходных данных, так и от их объема. Если обозначить значение параметра временной сложности алгоритма α символом Tα, а буквой V обозначить некоторый числовой параметр, характеризующий исходные данные, то временную сложность можно представить как функцию Tα(V). Выбор параметра V зависит от решаемой задачи или от вида используемого алгоритма для решения данной задачи. Пример 1. Оценим временную сложность алгоритма вычисления факториала целого положительного числа. Function Factorial(x:Integer): Integer; Var m,i: Integer; For i:=2 To x Do m:=ro*i; Подсчитаем общее число операций, выполняемых программой при данном значении x. Один раз выполняется оператор m:=1; тело цикла (в котором две операции: умножение и присваивание) выполняется х - 1 раз; один раз выполняется присваивание Factorial:=m. Если каждую из операций принять за единицу сложности, то временная сложность всего алгоритма будет 1 + 2 (x - 1) + 1 = 2х Отсюда понятно, что в качестве параметра следует принять значение х. Функция временной сложности получилась следующей: В этом случае можно сказать, что временная сложность зависит линейно от параметра данных - величины аргумента функции факториал. Пример 2. Вычисление скалярного произведения двух векторов А = (a1, a2, …, ak), В = (b1, b2, …, bk). For i:=l To k Do AB:=AB+A[i]*B[i]; В этой задаче объем входных данных п = 2k. Количество выполняемых операций 1 + 3k = 1 + 3(n/2). Здесь можно взять V= k= п/2. Зависимости сложности алгоритма от значений элементов векторов А и В нет. Как и в предыдущем примере, здесь можно говорить о линейной зависимости временной сложности от параметра данных. С параметром временной сложности алгоритма обычно связывают две теоретические проблемы. Первая состоит в поиске ответа на вопрос: до какого предела значения временной сложности можно дойти, совершенствуя алгоритм решения задачи? Этот предел зависит от самой задачи и, следовательно, является ее собственной характеристикой. Вторая проблема связана с классификацией алгоритмов по временной сложности. Функция Tα(V) обычно растет с ростом V. Как быстро она растет? Существуют алгоритмы с линейной зависимостью Тα от V (как это было в рассмотренных нами примерах), с квадратичной зависимостью и с зависимостью более высоких степеней. Такие алгоритмы называются полиномиальными. А существуют алгоритмы, сложность которых растет быстрее любого полинома. Проблема, которую часто решают теоретики - исследователи алгоритмов, заключается в следующем вопросе: возможен ли для данной задачи полиномиальный алгоритм? Функции, часто встречающиеся при анализе алгоритмов: Первые четыре функции имеют невысокую скорость роста и алгоритмы, время работы которых оценивается этими функциями, можно считать быстродействующими. Скорость роста экспоненциальной функции иногда характеризуют как «взрывную». Для сравнения допустим, что имеются алгоритмы, трудоемкость которых (число операций) достаточно точно отражается этими функциями. Пусть эти алгоритмы выполняются на компьютере, работающем со скоростью 10 12 операций в секунду. При длине входа n
≤ 100000 алгоритмы, скорость работы которых оценивается первыми четырьмя функциями, получат ответ за ничтожные доли секунды. Для алгоритма с трудоемкостью 2 n
время работы оценивается следующим образом: Вопрос 15=49. Последовательные, циклические и рекурсивные алгоритмы.
Последовательные алгоритмы
– алгоритмы, в которых блоки выполняются последовательно друг за другом, в порядке заданной схемы. Пример. Вычислить периметр треугольника со сторонами a,b,c.13 Алгоритм разветвляющейся структуры
На практике редко удается представить решение задачи в виде алгоритма линейной структуры. Часто в зависимости от каких-либо промежуточных результатов вычисления осуществляются либо по одним, либо по другим формулам, т.е. в зависимости от выполнения некоторого логического условия вычислительный процесс осуществляется по одной или другой формуле. Алгоритм такого вычислительного процесса называется алгоритмом разветвляющейся структуры. Ветвление - управляющая структура, организующая выполнение лишь одного из двух указанных действий в зависимости от справедливости некоторого условия. Условие - вопрос, имеющий два варианта ответа: да или нет. Запись ветвления выполняется в двух формах: полной и неполной (Рис. 1 а, б). а) полная форма б) неполная форма Циклические алгоритмы
–
алгоритмы, в которых приходится многократно вычислять значения по одним и тем же математическим зависимостям (блок схемам) для различных значений входящих в них величин. Использование циклов позволяет существенно сократить объем схемы алгоритма и длину соответствующей ей программы. Различают циклы с заданным и неизвестным числом повторений. С заданным числом повторений - цикл со счетчиком. С неизвестным числом повторений - цикл с предусловием, цикл с постусловием. Функция (или процедура), которая прямо или косвенно обращается к себе, называется рекурсивной. Рекурсия - метод определения функции через её предыдущие и ранее определенные значения, а так же способ организации вычислений, при котором функция вызывает сама себя с другим аргументом При реализации рекурсивных алгоритмов каждый шаг рекурсии не дает непосредственного решения задачи, но сводит ее к такой же задаче меньшего размера. Этот процесс должен приводить к задаче такого размера, когда решение получается достаточно легко. Далее "обратный ход" дает последовательные решения для задачи все большего размера, вплоть до первоначального. В основе реализации процедуры с рекурсией лежит стек (память "магазинного" типа), где хранятся данные, участвующие во всех вызовах процедуры, при которых она еще не завершила свою работу. Рекурсия – это способ организации процесса вычисления, когда алгоритм обращается сам к себе. Принцип рекурсии позволяет решить сложную задачу путем последовательного решения более простых подзадач.Как правило, рекурсия необходима в тех случаях, когда требуется перебрать слишком много вариантов. Рекурсию принято считать как одну из разновидностей циклического алгоритма. Рекурсивная форма организации позволяет придать алгоритму более компактный вид. Таким образом, решается проблема от сложного к простому – содержание рекурсивного алгоритма отражает более сложный объект через более простой такого же типа. Обычно рекурсивный алгоритм содержит следующие основные части: – условие для завершения цикла; – тело рекурсии, которое включает действия, предназначенные для выполнения на каждой итерации; – шаг рекурсии, на котором рекурсивный алгоритм вызывает сам себя. Различают прямую и косвенную рекурсию. В первом случае алгоритм содержит функцию, которая сама себя вызывает. Если функция вызывает другую функцию, которая, в свою очередь, вызывает первую, то такая функция называется косвенно рекурсивной. Основное требование к рекурсивным алгоритмам – процесс обращения не должен быть бесконечным. Другими словами, должна быть реализована проверка завершения вызова, или в рекурсивном определении должно присутствовать ограничение, при котором дальнейшая инициализация рекурсии прекращается. Примером рекурсивной функции является вычисление факториала числа. int factoria(int n)
if (n) return n* factoria(n-1);
else return 1;
Пример рекурсивной процедуры: Рассмотрим, что произойдет, если в основной программе поставить вызов, например, вида Rec(3). Ниже представлена блок-схема, показывающая последовательность выполнения операторов. Функция сложности
0(1). В алгоритмах константной сложности большинство операций в программе выполняются один или несколько раз. Любой алгоритм, всегда требующий (независимо от размера данных) одного и того же времени, имеет константную сложность. Функция сложности 0(N).
Время работы программы обычно линейно, когда каждый элемент входных данных требуется обработать лишь линейное число раз. Эта функция сложности характеризует простой цикл. Функция сложности 0(N 2), 0(N
3), 0(№) -
полиномиальная функция сложности: число операций растет пропорционально квадрату N.
В общем случае может быть О(Л^) в зависимости от сложности задачи. Эта функция сложности характеризует сложный цикл. Функция сложности
O(Log 2 (A0), 0(N
log 2 (A0). Такое время работают алгоритмы, которые делят большую проблему на множество небольших, а затем, решив их, объединяют решения. Функция сложности 0(e N).
Алгоритмы с экспоненциальной сложностью чаще всего возникают в результате подхода, именуемого методом грубой силы. Функция сложности 0(М) -
число операций растет пропорционально факториалу N.
Программист должен уметь проводить анализ алгоритмов и определять их сложность. Временная сложность алгоритма может быть подсчитана исходя из анализа его управляющих структур. Алгоритмы без циклов и рекурсивных вызовов имеют константную сложность. Если нет рекурсии и циклов, все управляющие структуры могут быть сведены к структурам константной сложности. Следовательно, и весь алгоритм также характеризуется константной сложностью. Определение сложности алгоритма, в основном, сводится к анализу циклов и рекурсивных вызовов. Например, рассмотрим алгоритм обработки элементов массива. For /": = 1 to N
do Begin Сложность этого алгоритма О
(А), так как тело цикла выполняется А раз, и сложность тела цикла равна 0(1). Если один цикл вложен в другой и оба цикла зависят от размера одной и той же переменной, то вся конструкция характеризуется квадратичной сложностью. For /: = 1 to N
do For j: =
1 to N
do Begin Сложность этой программы 0(N 2).
Пример 1.
Оценим сложность программы, вводящей с клавиатуры массив и находящей в нем наибольший элемент. Алгоритм состоит из следующих шагов: Сложим число операций А + (А - 1) + 1 = 2А, т.е. существует такая константа, что при любом А число операций не превышает СА. Следовательно, сложность алгоритма равна 0(A). Пример 2.
Оценим сложность программы, вводящей с клавиатуры массив и находящей в нем элемент с заданным свойством (например, равный определенному значению). Алгоритм состоит из следующих шагов: В лучшем случае указанный алгоритм потребует А + 2 операции (ввод всего массива, единственное сравнение, вывод), в худшем (когда такого элемента нет, 2А + 1 операцию). Если А будет большим числом, к примеру порядка 10 6 , то единицей можно пренебречь. Следовательно, сложность алгоритма равна 0(N).
Пример 3.
Определим функцию сложности алгоритма шифрования слова длиной L
методом подстановки. Пусть существует таблица, в которой для каждого символа алфавита записан символ, на который его надо заменить. Обозначим число букв алфавита S.
Алгоритм состоит из следующих шагов: Общее число операций 1 + (S +)L.
В случае достаточно больших S
и L
единицами можно пренебречь, и получится, что функция сложности приведенного алгоритма есть O(S L).
Пример 4.
Определим функцию сложности алгоритма перевода натурального числа 1
V в двоичную систему счисления (без операций ввода и вывода данных). Алгоритм состоит из следующих шагов: Общее число операций не превышает 1 + log 2 A. Поэтому описанный алгоритм имеет сложность 0(og 2 N).
2 m =
m=
Итак, O(log 2 n).
1. Программы, написанные на языке высокого уровня, транслируются в машинные коды, и понять сколько времени потребуется для выполнения того или иного оператора может быть трудно.
2. Многие программы очень чувствительны к входным данным, и их эффективность может очень сильно от них зависеть. Средний случай может оказаться математической фикцией не связанной с теми данными на которых программа используется, а худший случай маловероятен.
Объем вычислений при сортировке
1) для сложных алгоритмов получение O-оценок, как правило, либо очень трудоемко, либо практически невозможно,
2) часто трудно определить сложность "в среднем",
3) O-оценки слишком грубые для отображения более тонких отличий алгоритмов,
4) O-анализ дает слишком мало информации (или вовсе ее не дает) для анализа поведения алгоритмов при обработке небольших объемов данных.
procedure Rec(a: integer);
begin
if a>0 then
Rec(a-1);
writeln(a);
end;
