- •Глава 4
- •4.1. Комбинаторные вычисления на конечных множествах
- •4.1.2. Асимптотика
- •Говорят, что при Xx0 f(X) растёт медленнее, чем g(X), или что f(X) "есть о-малое" от g(X).
- •Отсюда, в частности, имеем при n
- •4.1.3. Рекуррентные соотношения
- •Последовательность Фибоначчи асимптотически растёт как
- •4.1.4. Производящие функции
- •4.2. Оценки сложности алгоритмов
- •4.3. Методы повышения эффективности алгоритмов
- •4.3.1. Рекурсия
- •4.3.2. Приём “разделяй и властвуй”
- •4.3.3 Принцип балансировки
- •4.3.4. Динамическое программирование
- •4.3.5. Алгоритмы с возвратом
- •Понимание постановки задачи
- •Составление плана решения
- •Взгляд назад
- •Основные этапы полного построения алгоритма
- •Постановка задачи
- •Временная сложность t(n)
- •Ёмкостная сложность е(n)
- •Заключение
- •Контрольные вопросы. Упражнения
4.3.3 Принцип балансировки
Разбиение задачи на подзадачи равных размеров с целью поддержания равновесия - основной руководящий принцип при разработке эффективного алгоритма. Балансировка полезна не только при использовании приема “разделяй и властвуй”; например, эффективные алгоритмы получаются в результате балансировки размеров поддеревьев, а также весов двух операций.
Рассмотрим задачу расположения целых чисел в порядке неубывания. Простейший способ сделать это - найти наименьший элемент, исследуя всю последовательность и затем меняя местами наименьший элемент с первым. Процесс повторяется на остальных n-1 элементах, и это повторение приводит к тому, что второй наименьший элемент оказывается на втором месте. Повторение процесса на остальных n-2, n-3,..., 2 элементах сортирует всю последовательность (этот процесс известен под названием “сортировка простым выбором“). Этот алгоритм приводит к рекуррентным уравнениям
для числа сравнений, произведенных между сортируемыми элементами. Решением этих уравнений служит Т(n)=n(n-1)/2, что составляет О(n2).
Хотя этот алгоритм можно считать рекурсивным применением приема “разделяй и властвуй”, он не эффективен для больших n, поскольку задача разбивается на неравные части (одна подзадача имеет размер i, а другая - n-i, где i - номер шага процесса решения задачи). Эффективнее будет решение, если разбить задачу на две подзадачи c размерами примерно n/2. Это выполняется методом, известным как сортировка слиянием.
Рассмотрим последовательность целых чисел х1, х2,..., хn. Снова предположим для простоты, что n - степень числа 2. Один из способов упорядочить эту последовательность - разбить ее на две подпоследовательности х1, х2, ... , хn/2 и xn/2+1, ... , хn, упорядочить каждую из них и затем слить их. Под “слиянием” понимают объединение двух уже упорядоченных последовательностей в одну упорядоченную последовательность.
Алгоритм 4.4. Сортировка слиянием
ВХОД. Последовательность чисел х1, x2,..., хn, где n - степень числа 2.
ВЫХОД. Последовательность чисел у1, y2,..., уn, которая является перестановкой входа и удовлетворяет неравенствам y1y2...yn .
МЕТОД. Применим процедуру MERGE(S, Т) (merge - слияние), входом которой служат две упорядоченные последовательности S и Т, а выходом - последовательность Q элементов из S и Т, расположенных в порядке неубывания. Поскольку S и Т упорядочены, MERGE требует сравнений не больше, чем сумма длин S и Т без единицы (|S| + |T| -1). Работа этой процедуры состоит в выборе большего из наибольших элементов, остающихся в S и Т, и в последующем удалении выбранного элемента и перезаписи его в Q. В случае совпадения можно отдавать предпочтение последовательности S. Кроме того, применяется процедура SORT(i, j) (см. ниже), сортирующая подпоследовательность xi, xi+1, ... , xj в предположении, что она имеет длину 2k для некоторого k0. Для сортировки исходной последовательности вызывается процедура SORT(1, n).
procedure SORT(i, j)
if i=j then return xi
else
begin
m(i+j-1)/2;
return MERGE(SORT(i, m), SORT(m+1, j))
end.
Подсчёт числа сравнений в алгоритме 4.4 приводит к рекуррентным уравнениям
решением которых по теореме 4.1 является Т(n)=О(nlog2n). Для больших n сбалансированность размеров подзадач даёт значительную выгоду. Аналогичный анализ показывает, что общее время работы процедуры SORT, затрачиваемое не только на сравнение, также есть О(nlog2n).