4. способы повышения эффективности алгоритмов

Алгоритм 4.4. Сортировка слиянием


ВХОД. Последовательность чисел х₁, x_2,..., х_n, где n - степень числа 2.
ВЫХОД. Последовательность чисел у₁, y₂,..., у_n, которая является перестановкой входа и удовлетворяет неравенствам y₁y₂...y_n .
МЕТОД. Применим процедуру MERGE(S,Т) (merge - слияние), входом которой служат две упорядоченные последовательности S и Т, а выходом - последовательность Q элементов из S и Т, расположенных в порядке неубывания. Поскольку S и Т упорядочены, MERGE требует сравнений не больше, чем сумма длин S и Т без единицы ( |S| + |T| -1 ). Работа этой процедуры состоит в выборе большего из наибольших элементов, остающихся в S и Т, и в последующем удалении выбранного элемента и перезаписи его в Q. В случае совпадения можно отдавать предпочтение последовательности S. Кроме того, применяется процедура SORT(i, j) (см.ниже), сортирующая подпоследовательность x_i,x_i+1,...,x_j в предположении, что она имеет длину 2^k для некоторого k0. Для сортировки исходной последовательности вызывается процедура SORT(1, n).


procedure SORT(i, j)
if i=j then return x_i
else
begin
m(i+j-1)/2;
return MEGRE(SORT(i, m),SORT(m+1, j))
end

Подсчет числа сравнений в алгоритме 4.4 приводит к рекуррентным уравнениям

решением которых по теореме 4.1 является Т(n)=О(nlog₂n). Для больших n сбалансированность размеров подзадач дает значительную выгоду. Аналогичный анализ показывает, что общее время работы процедуры SORT, затрачиваемое не только на сравнение, также есть О(nlog₂n).
4.2.4 Динамическое программирование

Рекурсивная техника полезна, если задачу можно разбить на подзадачи за разумное время, а суммарный размер подзадач будет небольшим. Из теоремы 4.1 вытекает, что если сумма размеров подзадач равна an для некоторой постоянной а>0, то рекурсивный алгоритм, вероятно, имеет полиномиальную временную сложность.

Но если очевидное разбиение задачи размера n сводит ее к n задачам размера n-1, то рекурсивный алгоритм, вероятно, имеет экспоненциальную сложность. В этом случае часто можно получить более эффективные алгоритмы с помощью табличной техники, называемой динамическим программированием.
В сущности, при динамическом программировании вычисляется решение для всех подзадач. Вычисление идет от малых подзадач к большим, и ответы запоминаются в таблице. Преимущество этого метода состоит в том, что раз уж задача решена, ее ответ где-то хранится и никогда не вычисляется заново.
Рассмотрим эту технику на примере вычисления произведения n матриц М=М₁ x М₂ x...x М_k , где M_i-матрица с r_i-1 строками и r_i столбцами. Порядок, в котором эти матрицы перемножаются, может существенно сказаться на общем числе операций, требуемых для вычисления М, независимо от алгоритма, применяемого для умножения матриц.
Пример 4.1.
Будем считать, что умножение (р x q)-матрицы на (q x r)-матрицу требует pqr операций, и рассмотрим произведение (в квадратных скобках указаны размерности матриц).
М= М₁ x М₂ x М₃ x М₄
[10 x 20] [20 x 50] [50 x 1] [1 x 100]
Если вычислять М в порядке М₁x (М₂x(М₃xМ₄)), то потребуется 125000 операций, тогда как вычисления в порядке (М₁x(М₂xМ₃))xМ₄ занимает лишь 2200 операций.
Процесс перебора всех порядков, в которых можно вычислить рассматриваемое произведение n матриц, с целью минимизации числа операций имеет экспоненциальную сложность, что при больших n практически неприемлемо. Однако динамическое программирование приводит к алгоритму сложности О(n³).


4.3. Заключение
При разработке эффективных алгоритмов необходимо использовать как структуры высокого уровня (списки, очереди, стеки ), так и мощную технику рекурсии и динамического программирования. Важными являются приемы общего вида “разделяй и властвуй” и “балансировка”. Существуют и другие методы повышения эффективности алгоритмов [...]. Разработчик алгоритмов должен изучить задачу с разных точек зрения, пока не убедится, что получил алгоритм, наиболее подходящий для его целей.