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

4.2.3 Принцип балансировки

Разбиение задачи на подзадачи равных размеров с целью поддержания равновесия - основной руководящий принцип при разработке эффективного алгоритма. Балансировка полезна не только при использовании приема “разделяй и властвуй”; например, эффективные алгоритмы получаются в результате балансировки размеров поддеревьев, а также весов двух операций.

Рассмотрим задачу расположения целых чисел в порядке неубывания. Простейший способ сделать это - найти наименьший элемент, исследуя всю последовательность и затем меняя местами наименьший элемент с первым. Процесс повторяется на остальных n-1 элементах, и это повторение приводит к тому, что второй наименьший элемент оказывается на втором месте.Повторение процесса на остальных n-2, n-3,..., 2 элементах сортирует всю последовательность (этот процесс известен под названием “сортировка простым выбором “. Этот алгоритм приводит к рекуррентным уравнениям


для числа сравнений, произведенных между сортируемыми элементами. Решением этих уравнений служит Т(n)=n(n-1)/2, что составляет О(n²).
Хотя этот алгоритм можно считать рекурсивным применением приема “разделяй и властвуй”, он не эффективен для больших n, поскольку задача разбивается на неравные части (одна подзадача имеет размер i, а другая - n-i, где i - номер шага процесса решения задачи). Эффективнее будет решение, если разбить задачу на две подзадачи c размерами примерно n/2. Это выполняется методом, известным как сортировка слиянием.
Рассмотрим последовательность целых чисел х₁, х₂,..., х_n. Снова предположим для простоты, что n-степень числа 2. Один из способов упорядочить эту последовательность - разбить ее на две подпоследовательности х₁, х₂,...,х_n/2 и x_(n/2+1, , х_n, упорядочить каждую из них и затем слить их. Под “слиянием” понимают объединение двух уже упорядоченных последовательностей в одну упорядоченную последовательность.