12.1   Алгоритмы "разделяй и властвуй"¶

Разделяй и властвуй (divide and conquer) - это очень важная и широко используемая стратегия построения алгоритмов. Обычно она реализуется через рекурсию и включает два этапа: "разделение" и "решение".

1. Разделение (этап декомпозиции): рекурсивно разбить исходную задачу на две или более подзадачи, пока не будет достигнута наименьшая подзадача.
2. Решение (этап объединения): начиная с уже известных решений наименьших подзадач, снизу вверх объединять решения подзадач и тем самым получать решение исходной задачи.

Как показано на рисунке 12-1, "сортировка слиянием" является одним из типичных примеров применения стратегии "разделяй и властвуй".

1. Разделение: рекурсивно разделить исходный массив (исходную задачу) на два подмассива (подзадачи), пока в подмассиве не останется только один элемент (наименьшая подзадача).
2. Решение: снизу вверх объединять упорядоченные подмассивы (решения подзадач), чтобы получить упорядоченный исходный массив (решение исходной задачи).

Рисунок 12-1   Стратегия divide and conquer в сортировке слиянием

12.1.1   Как определить задачу divide and conquer¶

Чтобы понять, подходит ли задача для решения методом divide and conquer, обычно можно ориентироваться на следующие критерии.

1. Задача раскладывается на части: исходную задачу можно разбить на более мелкие и похожие подзадачи, причем такое разбиение можно применять рекурсивно.
2. Подзадачи независимы: подзадачи не пересекаются, не зависят друг от друга и могут решаться независимо.
3. Решения подзадач можно объединить: решение исходной задачи получается объединением решений подзадач.

Очевидно, что сортировка слиянием удовлетворяет всем трем критериям.

1. Задача раскладывается на части: массив (исходная задача) рекурсивно делится на два подмассива (подзадачи).
2. Подзадачи независимы: каждый подмассив можно сортировать отдельно (то есть каждую подзадачу можно решать независимо).
3. Решения подзадач можно объединить: два упорядоченных подмассива (решения подзадач) можно объединить в один упорядоченный массив (решение исходной задачи).

12.1.2   Повышение эффективности с помощью divide and conquer¶

Стратегия divide and conquer не только позволяет эффективно решать алгоритмические задачи, но и часто повышает эффективность самих алгоритмов. Именно поэтому быстрая сортировка, сортировка слиянием и пирамидальная сортировка обычно работают быстрее, чем сортировка выбором, пузырьком и вставками.

Тогда возникает естественный вопрос: почему divide and conquer повышает эффективность алгоритма и какова логика этого на более глубоком уровне? Иными словами, почему разбиение большой задачи на несколько подзадач, решение этих подзадач и последующее объединение их решений оказывается эффективнее, чем прямое решение исходной задачи? Этот вопрос можно рассмотреть с двух сторон: через число операций и через параллельные вычисления.

1.   Оптимизация числа операций¶

Рассмотрим "сортировку пузырьком": для массива длины \(n\) ей требуется \(O(n^2)\) времени. Предположим, что мы разделим массив на два подмассива в середине, как показано на рисунке 12-2. Тогда само разбиение потребует \(O(n)\) времени, сортировка каждого подмассива займет \(O((n / 2)^2)\) времени, а объединение двух подмассивов потребует еще \(O(n)\) времени. Общая временная сложность будет равна:

Рисунок 12-2   Сортировка пузырьком до и после разбиения массива

Теперь рассмотрим следующее неравенство, в котором левая и правая части обозначают общее число операций до разбиения и после него:

Это означает, что при \(n > 4\) число операций после разбиения становится меньше, а значит, сортировка должна работать быстрее. При этом важно заметить, что временная сложность после разбиения все еще остается квадратичной, то есть \(O(n^2)\) ; уменьшается лишь константный множитель.

Если пойти дальше и продолжать делить каждый подмассив пополам, пока в нем не останется только один элемент, то мы фактически получим "сортировку слиянием", чья временная сложность равна \(O(n \log n)\) .

Можно пойти еще дальше и спросить: что если задать несколько точек разделения и равномерно разбить исходный массив на \(k\) подмассивов? Такая ситуация очень похожа на "блочную сортировку", которая особенно хорошо подходит для сортировки очень больших объемов данных и теоретически может достигать временной сложности \(O(n + k)\) .

2.   Оптимизация параллельных вычислений¶

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

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

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

Рисунок 12-3   Параллельные вычисления в блочной сортировке

12.1.3   Типичные применения divide and conquer¶

С одной стороны, divide and conquer можно использовать для решения многих классических алгоритмических задач.

• Поиск ближайшей пары точек: сначала множество точек делится на две части, затем ищется ближайшая пара в каждой части, а затем ближайшая пара, пересекающая границу между двумя частями.
• Умножение больших чисел: например, алгоритм Карацубы, который раскладывает умножение больших чисел на несколько умножений и сложений меньших чисел.
• Умножение матриц: например, алгоритм Штрассена, который раскладывает умножение больших матриц на несколько умножений и сложений матриц меньшего размера.
• Задача о Ханойской башне: задача о Ханойской башне решается рекурсивно и является типичным примером применения divide and conquer.
• Подсчет инверсий: если в последовательности предыдущее число больше следующего, то такая пара образует инверсию. Эту задачу можно решить с помощью идей divide and conquer, опираясь на сортировку слиянием.

С другой стороны, divide and conquer очень широко применяется при проектировании алгоритмов и структур данных.

• Двоичный поиск: двоичный поиск делит отсортированный массив на две части по индексу середины, а затем, в зависимости от результата сравнения целевого значения со средним элементом, исключает одну из половин и повторяет ту же операцию на оставшемся интервале.
• Сортировка слиянием: она уже была рассмотрена в начале этого раздела, поэтому не будем повторяться.
• Быстрая сортировка: в ней выбирается опорное значение, после чего массив делится на два подмассива: один содержит элементы меньше опорного, а другой - больше. Затем такая же операция повторяется для обеих частей, пока в подмассиве не останется один элемент.
• Блочная сортировка: ее основная идея заключается в распределении данных по нескольким блокам, сортировке элементов внутри каждого блока и последующем последовательном извлечении элементов из блоков для построения отсортированного массива.
• Деревья: например, двоичные деревья поиска, AVL-деревья, красно-черные деревья, B-деревья, B+ деревья и т.д. Их операции поиска, вставки и удаления можно рассматривать как применение divide and conquer.
• Кучи: куча является особым видом полного бинарного дерева, а такие операции, как вставка, удаление и упорядочивание, по сути содержат идеи divide and conquer.
• Хеш-таблицы: хотя хеш-таблицы напрямую не используют divide and conquer, некоторые способы разрешения коллизий косвенно опираются на эту стратегию. Например, длинные цепочки в методе цепочек могут преобразовываться в красно-черные деревья для повышения эффективности поиска.

Нетрудно заметить, что divide and conquer - это "тихая" алгоритмическая идея, скрыто присутствующая внутри самых разных алгоритмов и структур данных.

Оставляйте свои идеи, вопросы и предложения в комментариях