Как определить емкостную сложность алгоритма

Оценка сложности алгоритмов

Не так давно мне предложили вести курс основ теории алгоритмов в одном московском лицее. Я, конечно, с удовольствием согласился. В понедельник была первая лекция на которой я постарался объяснить ребятам методы оценки сложности алгоритмов. Я думаю, что некоторым читателям Хабра эта информация тоже может оказаться полезной, или по крайней мере интересной.
Существует несколько способов измерения сложности алгоритма. Программисты обычно сосредотачивают внимание на скорости алгоритма, но не менее важны и другие показатели – требования к объёму памяти, свободному месте на диске. Использование быстрого алгоритма не приведёт к ожидаемым результатам, если для его работы понадобится больше памяти, чем есть у компьютера.

Память или время

Многие алгоритмы предлагают выбор между объёмом памяти и скоростью. Задачу можно решить быстро, использую большой объём памяти, или медленнее, занимая меньший объём.
Типичным примером в данном случае служит алгоритм поиска кратчайшего пути. Представив карту города в виде сети, можно написать алгоритм для определения кратчайшего расстояния между двумя любыми точками этой сети. Чтобы не вычислять эти расстояния всякий раз, когда они нам нужны, мы можем вывести кратчайшие расстояния между всеми точками и сохранить результаты в таблице. Когда нам понадобится узнать кратчайшее расстояние между двумя заданными точками, мы можем просто взять готовое расстояние из таблицы.
Результат будет получен мгновенно, но это потребует огромного объёма памяти. Карта большого города может содержать десятки тысяч точек. Тогда, описанная выше таблица, должна содержать более 10 млрд. ячеек. Т.е. для того, чтобы повысить быстродействие алгоритма, необходимо использовать дополнительные 10 Гб памяти.
Из этой зависимости проистекает идея объёмно-временной сложности. При таком подходе алгоритм оценивается, как с точки зрении скорости выполнения, так и с точки зрения потреблённой памяти.
Мы будем уделять основное внимание временной сложности, но, тем не менее, обязательно будем оговаривать и объём потребляемой памяти.

Оценка порядка

При сравнении различных алгоритмов важно знать, как их сложность зависит от объёма входных данных. Допустим, при сортировке одним методом обработка тысячи чисел занимает 1 с., а обработка миллиона чисел – 10 с., при использовании другого алгоритма может потребоваться 2 с. и 5 с. соответственно. В таких условиях нельзя однозначно сказать, какой алгоритм лучше.
В общем случае сложность алгоритма можно оценить по порядку величины. Алгоритм имеет сложность O(f(n)), если при увеличении размерности входных данных N, время выполнения алгоритма возрастает с той же скоростью, что и функция f(N). Рассмотрим код, который для матрицы A[NxN] находит максимальный элемент в каждой строке.
for i:=1 to N do
begin
max:=A[i,1];
for j:=1 to N do
begin
if A[i,j]>max then
max:=A[i,j]
end;
writeln(max);
end;
В этом алгоритме переменная i меняется от 1 до N. При каждом изменении i, переменная j тоже меняется от 1 до N. Во время каждой из N итераций внешнего цикла, внутренний цикл тоже выполняется N раз. Общее количество итераций внутреннего цикла равно N*N. Это определяет сложность алгоритма O(N^2).
Оценивая порядок сложности алгоритма, необходимо использовать только ту часть, которая возрастает быстрее всего. Предположим, что рабочий цикл описывается выражением N^3+N. В таком случае его сложность будет равна O(N^3). Рассмотрение быстро растущей части функции позволяет оценить поведение алгоритма при увеличении N. Например, при N=100, то разница между N^3+N=1000100 и N=1000000 равна всего лишь 100, что составляет 0,01%.
При вычислении O можно не учитывать постоянные множители в выражениях. Алгоритм с рабочим шагом 3N^3 рассматривается, как O(N^3). Это делает зависимость отношения O(N) от изменения размера задачи более очевидной.

Определение сложности

Наиболее сложными частями программы обычно является выполнение циклов и вызов процедур. В предыдущем примере весь алгоритм выполнен с помощью двух циклов.
Если одна процедура вызывает другую, то необходимо более тщательно оценить сложность последней. Если в ней выполняется определённое число инструкций (например, вывод на печать), то на оценку сложности это практически не влияет. Если же в вызываемой процедуре выполняется O(N) шагов, то функция может значительно усложнить алгоритм. Если же процедура вызывается внутри цикла, то влияние может быть намного больше.
В качестве примера рассмотрим две процедуры: Slow со сложностью O(N^3) и Fast со сложностью O(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

end;
procedure Fast;
var
i,j: integer;
begin
for i:=1 to N do
for j:=1 to N do
Slow;
end;
procedure Both;
begin
Fast;
end;
Если во внутренних циклах процедуры Fast происходит вызов процедуры Slow, то сложности процедур перемножаются. В данном случае сложность алгоритма составляет O(N^2 )*O(N^3 )=O(N^5).
Если же основная программа вызывает процедуры по очереди, то их сложности складываются: O(N^2 )+O(N^3 )=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 Both;
begin
Fast;
Slow;
end;

Сложность рекурсивных алгоритмов

Простая рекурсия

Напомним, что рекурсивными процедурами называются процедуры, которые вызывают сами себя. Их сложность определить довольно тяжело. Сложность этих алгоритмов зависит не только от сложности внутренних циклов, но и от количества итераций рекурсии. Рекурсивная процедура может выглядеть достаточно простой, но она может серьёзно усложнить программу, многократно вызывая себя.
Рассмотрим рекурсивную реализацию вычисления факториала:
function Factorial(n: Word): integer;
begin
if n > 1 then
Factorial:=n*Factorial(n-1)
else
Factorial:=1;
end;
Эта процедура выполняется N раз, таким образом, вычислительная сложность этого алгоритма равна O(N).

Многократная рекурсия

Рекурсивный алгоритм, который вызывает себя несколько раз, называется многократной рекурсией. Такие процедуры гораздо сложнее анализировать, кроме того, они могут сделать алгоритм гораздо сложнее.
Рассмотрим такую процедуру:
procedure DoubleRecursive(N: integer);
begin
if N>0 then
begin
DoubleRecursive(N-1);
DoubleRecursive(N-1);
end;
end;
Поскольку процедура вызывается дважды, можно было бы предположить, что её рабочий цикл будет равен O(2N)=O(N). Но на самом деле ситуация гораздо сложнее. Если внимательно исследовать этот алгоритм, то станет очевидно, что его сложность равна O(2^(N+1)-1)=O(2^N). Всегда надо помнить, что анализ сложности рекурсивных алгоритмов весьма нетривиальная задача.

Объёмная сложность рекурсивных алгоритмов

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

Средний и наихудший случай

Оценка сложности алгоритма до порядка является верхней границей сложности алгоритмов. Если программа имеет большой порядок сложности, это вовсе не означает, что алгоритм будет выполняться действительно долго. На некоторых наборах данных выполнение алгоритма занимает намного меньше времени, чем можно предположить на основе их сложности. Например, рассмотрим код, который ищет заданный элемент в векторе A.
function Locate(data: integer): integer;
var
i: integer;
fl: boolean;
begin
fl:=false; i:=1;
while (not fl) and (i <=N) do
begin
if A[i]=data then
fl:=true
else
i:=i+1;
end;
if not fl then
i:=0;
Locate:=I;
end;
Если искомый элемент находится в конце списка, то программе придётся выполнить N шагов. В таком случае сложность алгоритма составит O(N). В этом наихудшем случае время работы алгоритма будем максимальным.
С другой стороны, искомый элемент может находится в списке на первой позиции. Алгоритму придётся сделать всего один шаг. Такой случай называется наилучшим и его сложность можно оценить, как O(1).
Оба эти случая маловероятны. Нас больше всего интересует ожидаемый вариант. Если элемента списка изначально беспорядочно смешаны, то искомый элемент может оказаться в любом месте списка. В среднем потребуется сделать N/2 сравнений, чтобы найти требуемый элемент. Значит сложность этого алгоритма в среднем составляет O(N/2)=O(N).
В данном случае средняя и ожидаемая сложность совпадают, но для многих алгоритмов наихудший случай сильно отличается от ожидаемого. Например, алгоритм быстрой сортировки в наихудшем случае имеет сложность порядка O(N^2), в то время как ожидаемое поведение описывается оценкой O(N*log(N)), что много быстрее.

Общие функции оценки сложности

Сейчас мы перечислим некоторые функции, которые чаще всего используются для вычисления сложности. Функции перечислены в порядке возрастания сложности. Чем выше в этом списке находится функция, тем быстрее будет выполняться алгоритм с такой оценкой.
1. C – константа
2. log(log(N))
3. log(N)
4. N^C, 0 5. N
6. N*log(N)
7. N^C, C>1
8. C^N, C>1
9. N!
Если мы хотим оценить сложность алгоритма, уравнение сложности которого содержит несколько этих функций, то уравнение можно сократить до функции, расположенной ниже в таблице. Например, O(log(N)+N!)=O(N!).
Если алгоритм вызывается редко и для небольших объёмов данных, то приемлемой можно считать сложность O(N^2), если же алгоритм работает в реальном времени, то не всегда достаточно производительности O(N).
Обычно алгоритмы со сложностью N*log(N) работают с хорошей скоростью. Алгоритмы со сложностью N^C можно использовать только при небольших значениях C. Вычислительная сложность алгоритмов, порядок которых определяется функциями C^N и N! очень велика, поэтому такие алгоритмы могут использоваться только для обработки небольшого объёма данных.
В заключение приведём таблицу, которая показывает, как долго компьютер, осуществляющий миллион операций в секунду, будет выполнять некоторые медленные алгоритмы.

Ёмкостная сложность алгоритма

Ёмкостная сложность алгоритма(Space complexity of an algorithm) — один из параметров, характеризующих алгоритм; определяется объемом памяти, использованным алгоритмом как функцией размера задачи.

См. также

Литература

• Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.

• Липский В. Комбинаторика для программистов. — М.: Мир, 1988.

Меpы сложности алгоpитмов (оценка алгоритмов) Понятие сложности

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

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

Когда при решении некоторой задачи есть несколько разных алгоритмов и стоит задача выбора одного из них для реализации, необходима оценка алгоритма с использованием некоторого критерия.

Критерием оптимальности алгоритма выбрана количественная характеристика – сложность алгоритма.

Виды сложностей алгоритма:

Емкостная сложность алгоритма

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

Но память не является критическим ресурсом для современных ВМ.

Временная сложность алгоритма

Чаще всего под анализом сложности алгоритма понимают исследование времени, необходимого для его выполнения.

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

т.е. физическое время выполнения алгоритма должно зависеть от количества выполняемых в алгоритме команд и времени их выполнения:

i*t, где

i — число действий (элементарных операций, команд),

элементарные операции – это операции, из которых складывается алгоритм решения задачи (:=, <>, =, +, –, *, /; and, or, not, xor; call, return)

t — среднее время выполнения одного элементарного действия, зависит от скорости обработки сигналов ВМ.

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

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

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

Если размер выхода не превосходит размер входа, то временную сложность можно рассматривать как функцию только размера входных данных.

T(N) — функция временной сложности (трудоемкости) — зависимость времени работы от количества входных данных N – размер задачи.

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

Кроме того, точное значение количества операций, выполненных алгоритмом, не играет существенной роли в его анализе, т.к. не является качественным показателем эффективности алгоритма.

Более важной оказывается скорость роста числа выполняемых операций при возрастании объема входных данных.

Два алгоритма можно сравнить по скорости роста сложности алгоритма.

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

Именно эта характеристика часто и фигурирует как оценка вычислительной сложности алгоритма.

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

Вычислительная сложность алгоритмов по-разному зависит от входных данных:

• только от объема данных
• От значений данных
• От порядка поступления данных
• От всех перечисленных выше факторов

Например, многие алгоритмы сортировки потратят гораздо меньше времени на упорядочивание массива, если он уже отсортирован.

Обычно у задачи есть какой-нибудь естественный параметр, характеризующий объем входных данных, и сложность оценивается по отношению к этому параметру

Размер входа определяется для каждой задачи индивидуально.

Например, размером входа принято считать:

• в задачах обработки одномерных массивов — количество элементов в массиве;
• в задачах обработки двумерных массивов — количество элементов в массиве или количество строк и столбцов массива;
• в задачах обработки чисел (длинная арифметика, проверка на простоту и т.д.) — общее число битов, необходимое для представления данных в памяти ВМ;
• в задачах обработки графов — количество вершин графа или число вершин и число ребер графа.

Т.о. время выполнения алгоритма T зависит от объема входных данных N:

где T – время выполнения алгоритма, мс;

Для построения аналитической зависимости скорости роста:

• оценивают функциюT(N) при некотором интервале[Nmin,Nmax]
• Проводят аппроксимацию этой кривой с помощью некоторой аналитической функцииf(N),поведение которой хорошо исследовано
• Изменяют параметры функции и оценивают ошибкиаппроксимации.

По виду функции f(N) алгоритмы разделяются на следующие классы:

• С линейной оценкой сложности, если функция f(N) = C·N ;

• С квадратичной сложностью, если

f(N) = C · N 2 ;

• С полиномиальной сложностью, если

f(N) = C₀ + C₁· N +…+ C_k · N k ;

• С факториальной сложностью, если f(N) =C·N!;
• С экспоненциальной сложностью, если f(N) = C · aN ;
• С гиперэкспоненциальной сложностью, если f(N) = C · a t, где t = aN .

Здесь C, a и k = некоторые константы, при этом число C может быть очень большим.

Скорость роста определяется старшим – доминирующим членом формулы.

Отбросив все младшие члены получаем порядок функции или алгоритма.

Эта функция является скоростью роста сложности алгоритма.

Сложность задачи (кол-во операций)

24. Вычислительная и емкостная сложность алгоритма

Физическое время реализации алгоритма при некотором наборе входных данных может быть определено как , где — количество операций i-ого типа, — время выполнения операции i-го типа, n – количество типов операций. Для одного и того же алгоритма при заданном наборе входных данных время t зависит от языка программирования и быстродействия конкретной ЭВМ. Если мы имеем такую оценку для нескольких алгоритмов решения одной и той же задачи, реализованных на разных языках и предназначенных для выполнения на ЭВМ с различным быстродействием, очевидно, что объективный выбор алгоритма выполнить невозможно. Можно принять за эталон некоторую операцию и, зная отношение времени выполнения i-й операции ко времени выполнения эталонной, можно определить суммарное число эталонных операций:

. Коэффициенты можно трактовать как относительное количество тактов . Объективная мера временной сложности алгоритма должна быть машинно- и программно-независимой. В качестве такой меры может выступать или .

, где — отношение количества тактов выполнения i-й операции к количеству тактов выполнения эталонной; — количество тактов выполнения алгоритма при заданном наборе входных данных.

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

Временная и вычислительная сложность являются функцией от размера входа. Размер входа – скаляр, если количество, например, некоторых действий или шагов зависит только от одного параметра входа задачи. Например, в задачах на графах – только от количества вершин или рёбер. Размер входа – вектор, если от нескольких: для графов – количество вершин, рёбер, локальной степени вершин и т. д.

Понятие вычислительной сложности

Пусть A – алгоритм решения некоторого класса задач, а n – размерность задачи этого класса, тогда вычислительная сложность алгоритма – это некоторая функция , отображающая размерность задачи в «математическое» время ее решения, то есть дающая оценку количества некоторых операций, необходимых для решения данным алгоритмом любой задачи данного класса как функции от n. Функция f_A(n) является критерием качества алгоритма с точки зрения возможных временных затрат. Эффективным является понятие полиномиальный алгоритм, у которого растет не быстрее, чем полином от n. Алгоритм, имеющий экспоненциальную сложность: , пригоден для решения задач ограниченной размерности. Такие задачи определяют принадлежащими к классу NP – non-polynomial.

Вычислительная сложность, так же как и погрешность, может иметь оценку в лучшем и в худшем. Оценка в худшем (сверху) получается в том случае, если входные данные являются худшими из возможных. Например, для задачи на графах, предположение, что граф – полный.

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

Однако ориентация на худший случай нередко приводит к пессимистическим оценкам, которые могут привести к неправильному выбору используемого алгоритма. Более реалистичной является оценка в среднем. Для задач на графы такая оценка появляется при предположении, что граф – однородный с некоторой средней степенью вершин.

Емкостная сложность алгоритма

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

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

Вычислительная и ёмкостная сложность скоррелированы: как правило, снижение вычислительной сложности достигается за счёт увеличения ёмкостной и наоборот. В качестве обобщенной характеристики сложности алгоритма было предложено использовать так называемый коэффициент сложности , где N – суммарное количество эталонных (или доминирующих) операций, V – общий объем памяти.