Как оценить сложность алгоритма

 Анализ скорости выполнения алгоритмов

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

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

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

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

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

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

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

Оценка порядка сложности алгоритма

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

В общем случае сложность алгоритма можно оценить по порядку величины. Алгоритм имеет сложность O(f(n)), если при увеличении размерности входных данных N, время выполнения алгоритма возрастает с той же скоростью, что и функция f(n). Рассмотрим код, который для матрицы A[N x N] находит максимальный элемент в каждой строке.

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 x N. Это определяет сложность алгоритма O(N²).

Оценивая порядок сложности алгоритма, необходимо использовать только ту часть, которая возрастает быстрее всего. Предположим, что рабочий цикл описывается выражением N³ + N. В таком случае его сложность будет равна O(N³). При вычислении можно не учитывать постоянные множители в выражениях. Алгоритм с рабочим шагом 3N³ рассматривается, как O(N³). Это делает зависимость отношения O(N) от изменения размера задачи более очевидной.

Читать полностью >>> http://habrahabr.ru/post/104219/