Лекция: Merge(out1, out2, size1, sorted);
farfree(out1); farfree(out2); // Освобождение динамической памяти
}
} // Конец Sorting
void Merge(int *out1, int *out2, unsigned size, int *sorted)
// Слияние двух отсортированных в неубывающем порядке подмассивов в один
{
unsigned ind1=0, ind2=0;
while ((ind1<size)&&(ind2<size))
{
if (out1[ind1] < out2[ind2]) *sorted++=out1[ind1++];
else *sorted++=out2[ind2++];
if (ind1==size)
while (ind2<size) *sorted++=out2[ind2++];
if (ind2==size)
while (ind1<size) *sorted++=out1[ind1++];
}
} // Конец Merge
Работа функции Merge состоит в выборе наименьшего из наименьших элементов сливаемых массивов и занесении его в выходной массив. После этого выбранный элемент удаляется из рассматриваемых массивов, и происходит сравнение следующих двух наименьших чисел. Поскольку сливаемые множества S и T сами уже упорядочены, то подобная процедура не требует числа сравнений, большего, чем сумма длин S и T без единицы.
Подсчёт числа сравнений в алгоритме 6 приводит к рекуррентным уравнениям
, (1.10)
решением которых по теореме 1 является C(n)=O(n×logn). Для больших n сбалансированность размеров подзадач дала значительную выгоду.
Ещё один важный момент данной программы заключается в том, что функция Sorting использует динамическую память для сливаемых подмассивов, которая выделяется и освобождается по мере надобности. Данный приём используется очень часто для представления структур, связанных со списками и деревьями.
1.9 Динамическое программирование
Рекурсивная техника полезна, если задачу можно разбить на подзадачи за разумное время, а суммарный размер подзадач будет небольшим. Из теоремы 1 следует, что если сумма размеров подзадач равна a×n для некоторой постоянной a>1, то рекурсивный алгоритм, вероятно, имеет полиномиальную временную сложность. Однако если очевидное разбиение задачи размера n сводит её к n подзадачам размера n-1, то рекурсивный алгоритм, вероятно, имеет экспоненциальную сложность. В этом случае часто можно получить более эффективные алгоритмы с помощью техники, называемой динамическим программированием (dynamic programming).
Динамическое программирование вычисляет решения для всех подзадач. Вычисление идёт от малых подзадач к бóльшим, и ответы запоминаются в таблице. Преимущество этого метода состоит в том, что раз уж подзадача решена, её ответ где-то хранится и никогда не вычисляется заново. Попробуем рассмотреть данную технику на простом примере.
Пусть требуется вычислить произведение n матриц
M = M1´M2´…´Mn,
где Mi — матрица с числом строк ri-1 и числом столбцов ri (размера ri-1´ri). Порядок, в котором перемножаются данные матрицы, может существенно сказаться на общем числе операций, требуемых для вычисления M, независимо от алгоритма, используемого для умножения матриц.
Пример 1.7. Предположим, что для умножения матрицы размера (p´q) на матрицу (q´r) требуется p´q´r операций, как это бывает в «обычном» алгоритме, и рассмотрим произведение:
M = M1 ´ M2 ´ M3,
(10´20) (20´1) (1´50)
где внизу указаны размеры матриц. Если теперь вычислить M в порядке M1´(M2´M3), то потребуется 11000 операций. Когда же произведение M будет вычислено в порядке (M1´M2)´M3, то потребуется всего 700 операций.ð
Доказано, что процесс перебора всех возможных порядков, в которых можно вычислить рассматриваемое произведение n матриц, с целью минимизировать число операций имеет экспоненциальную сложность O(2n), что для больших n практически неприемлемо. Однако динамическое программирование приводит к алгоритму сложности O(n3). Пусть mij — минимальная сложность вычисления Mi´Mi+1´…´Mj (1£i£ j£ n). Очевидно, что
(1.11)
Здесь mik — минимальная сложность вычисления M′=Mi+1´Mi+2´…´Mk, а mk+1,j — минимальная сложность вычисления M″=Mk+1´Mk+2´…´Mj. Третье слагаемое равно сложности умножения M′ на M″. Поскольку матрица M′ имеет размер ri-1´rk, а матрица M″ — размер rk´rj. В (1.11) утверждается, что mij (j > i) — наименьшая из сумм этих трёх членов по всем возможным значениям k, лежащим между i и j-1.
При динамическом программировании mij вычисляются в порядке возрастания разностей нижних индексов. Начинают с вычисления mii для всех i, затем mi,i+1 для всех i, потом mi,i+2 и т.д. При этом mik и mk+1,j в (1.11) будут уже вычислены, до того, как приступают к вычислению mij. Это следует из того, что при i £ k < j разность j-i должна быть больше k-i, а также и j-(k+1).
Алгоритм 7. Динамического программирования для вычисления порядка, минимизирующего сложность умножения цепочки из n матриц M1´M2´…´Mn
Вход. r0, r1, …, rn, где ri-1 и ri — числа строк и столбцов матрицы Mi.
Выход. Минимальная сложность умножения матриц Mi в предположении, что для умножения (p´q)-матрицы на (q´r)-матрицу требуется p×q×r операций.
Метод. Алгоритм заполняет последовательно «верхнетреугольную» матрицу минимальных сложностей умножения двух, трех, четырех, … и т.д. матриц из предлагаемой последовательности. На первом шаге заполняется строка, соответствующая сложности умножения двух матриц, взятых последовательно из предлагаемого произведения. На втором шаге рассчитываются минимальные сложности умножения трёх последовательных матриц, основываясь на известных минимальных сложностях умножения двух матриц. Заполняется соответствующая строка, и т.д.