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



              

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


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

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

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

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

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

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

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


Содержание  Назад  Вперед