Параллельное программирование

Сложность алгоритма и проблема распараллеливания


Ранее уже использовалось понятие сложности. Рассмотрим его полнее.

Пусть задан некоторый алгоритм A. Почти всегда существует параметр n, характеризующий объем его данных. Пусть функция T(n) — время выполнения A, а f — некоторая функция от n. Говорят, что алгоритм A имеет теоретическую (асимптотическую) сложность O(f(n)), если

,

где k — действительное.

Если алгоритм выполняется за фиксированное время, не зависящее от размера задачи, говорят, что его сложность равна O(1).

Это определение обобщается в случае, если время выполнения существенно зависит от нескольких параметров. Например, алгоритм, определяющий, входит ли множество m элементов в множество n элементов, может иметь, в зависимости от используемых структур данных, сложность O (m n) или O (m+n).

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

  • максимальную сложность, определяемую значением Tmax(n) — время выполнения алгоритма, когда выбранный набор n данных порождает наиболее долгое время выполнения алгоритма;
  • среднюю сложность, определяемую значением Tср(n) — средним временем выполнения алгоритма, примененного к n произвольным данным.

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

Самыми лучшими являются линейные алгоритмы, имеющие сложность порядка an=b. Они называются также алгоритмами порядка O(n) где n — размерность входных данных. Такие алгоритмы действительно существуют. Например, сложение двух чисел столбиком в случае, если одно из них состоит из n, а другое — из m цифр, требует не более max(n, m) сложений и не более max(n, m) запоминаний. Т.е. данный алгоритм имеет сложность порядка O(n+m). Разумеется, это выражение показывает только порядок величины — постоянные факторы в нем не учитываются.


Обобщение линейности дает нам первый большой класс алгоритмов — полиномиальных.

Полиномиальным (или алгоритмом полиномиальной временной сложности) называется алгоритм, у которого временная сложность есть O(p(n)), где p(n) — полином от n. Задачи, где для решения известен алгоритм, сложность которого составляет полином заданной, постоянной и не зависящей от размерности входной величины n степени, называют "хорошими" и относят их к классу P.

Экспоненциальной по природе считается задача сложностью не менее порядка xn, где x — константа или полином от n. Например, это задачи, в которых возможное число ответов уже экспоненциально. В частности, к ним относятся задачи, где требуется построить все подмножества заданного множества или все поддеревья заданного графа. Экспоненциальные задачи относят к классу E.

Соответственно, и алгоритмы, в оценку сложности которых n входит в показатель степени, относятся к экспоненциальным.

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

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

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

Таблица 3.1. Сложность и время выполненияСложностьРазмер задачи — n102030405060nn?n?n52n3n
0.00001 с0.00002 с0.00003 с0.00004 с0.00005 с0.00006 с
0.0001 с0.0004 с0.0009 с0.0016 с0.0025 с0.0036 с
0.001 с0.008 с0.027 с0.064 с0.125 с0.216 с
0.1 с3.2 с24.3 с1.7 мин5.2 мин13.0 мин
0.01 с1.0 с17.9 мин12.7 дней35.7 лет366 веков
0.59 с58 мин6.5 лет3855 веков2·108 веков1.3·1013 веков


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

Уточним понятие сложности для итеративных и рекурсивных алгоритмов.

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

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

Для большинства конечно-разностных схем решения дифференциальных уравнений методом сеток можно считать, что сложность одной итерации составляет O(n2) или O(n ? m), где n2 — количество узлов при равном разбиении по x и по y, а n? m — то же количество при различающемся разбиении по осям. Увеличение количества узлов, покрывающих ту же область, т.е. уменьшение hx и hy, увеличивает скорость сходимости - и, соответственно, уменьшает число итераций, но сложность каждой итерации растет квадратично. Значит, необходим компромисс, который достигается посредством изучения поведения процесса, как на теоретическом, так и на экспериментальном уровне, вплоть до автоматической коррекции шагов в процессе вычислений в зависимости от локального поведения аппроксимаций производных. Т.е. шаги становятся непостоянными во всей области.

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

Имеется широко распространенное соглашение, по которому задача не считается "хорошо решаемой", пока для нее не получен полиномиальный алгоритм.


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

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

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

Полиномиальные по сложности алгоритмы относят к классу P-сложных. Среди экспоненциальных выделяют алгоритмы, основанные на переборе, и их относят в класс NP-сложных. Т.е. формально возможно существование экспоненциальных алгоритмов, основанных не на переборе. Например, n!, растущий быстрее, чем 2n. К NP-сложным относятся, например, задачи линейного целочисленного программирования, составление расписания, поиск кратчайшего пути в лабиринте и т.д. Обратим внимание, что все это так называемые дискретные задачи — на основе "неделимых" объектов.

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


Содержание раздела