Разделяй и властвуй (информатика)

Ранними примерами таких алгоритмов являются в первую очередь «уменьшай и властвуй» — исходная задача последовательно разбивается на отдельные подзадачи, и в действительности может быть решена итеративно. Двоичный поиск, в котором подзадачи имеют примерно половину исходного размера, известен со времён Вавилона, хотя чёткое описание как компьютерного алгоритма получил в 1946 году в статье Джона Мокли^[4]. Ещё один древний алгоритм типа «уменьшай и властвуй» — алгоритм Евклида для вычисления наибольшего общего делителя из двух чисел путём уменьшения чисел до меньших и меньших эквивалентных подзадач, который датируется несколькими веками до нашей эры.

Ранний пример алгоритма «разделяй и властвуй» с несколькими подзадачами — гауссово (1805) описание метода, известного в современности как быстрое преобразование Фурье Кули — Тьюки^[5].

Ранний алгоритм «разделяй и властвуй» из двух подзадач, который был специально разработан для компьютеров и должным образом проанализирован, является алгоритмом сортировки слиянием, изобретённый Джоном фон Нейманом в 1945 году.^[6]

Типичный пример — алгоритм сортировки слиянием. Чтобы отсортировать массив чисел по возрастанию, он разбивается на две равные части, каждая сортируется, затем отсортированные части сливаются в одну. Эта процедура применяется к каждой из частей до тех пор, пока сортируемая часть массива содержит хотя бы два элемента (чтобы можно было её разбить на две части). Время работы этого алгоритма составляет ${\displaystyle O(n\log n)}$  операций, тогда как более простые алгоритмы требуют ${\displaystyle O(n^{2})}$  времени, где ${\displaystyle n}$  — размер исходного массива.

Ещё один примечательный пример — это алгоритм Карацубы^[7] умножения двух чисел из ${\displaystyle n}$  цифр путём ${\displaystyle O(n^{\log _{2}3})}$  числа операции. Этот алгоритм опроверг гипотезу Колмогорова 1956 года о том, что для этой задачи потребовалось бы ${\displaystyle O(n^{2})}$  операций.

В качестве ещё одного примера изначально некомпьютерного алгоритма «разделяй и властвуй» Кнут приводит метод маршрутизации почтовых отправлений: письма сортируются в отдельные пакеты, предназначенные для разных географических районов, каждый из этих пакетов делится на партии для более мелких подрайонов и так далее, пока они не будут доставлены^[4]. На том же принципе основе реализована с поразрядная сортировка перфокарт (IBM, 1929)^[4].

«Разделяй и властвуй» — мощный инструмент для решения концептуально сложных задач: все, что требуется для этого, — это найти случай разбивания задачи на подзадачи, решения тривиальных случаев и объединения подзадач в исходную задачу. Аналогично, «уменьшай и властвуй» требует только свести проблему к одной меньшей проблеме, такой как классическая Ханойская башня, которая сводит решение к перемещению башни высоты n к перемещению башни высоты n − 1.

Парадигма часто помогает в открытии эффективных алгоритмов. Это послужило ключом, например, к быстрому методу умножения Карацубы, алгоритмам быстрой сортировки и сортировки слиянием, алгоритму Штрассена для умножения матриц и быстрых преобразований Фурье.

Во всех этих примерах подход «разделяй и властвуй» привёл к улучшению асимптот��ческой стоимости решения в самом решении. Например, если базовый вариант имеет размер, ограниченный постоянной, то работа по разбиению задачи и объединению частичных решений пропорциональна размеру задачи ${\displaystyle n}$  и существует ограниченное число ${\displaystyle p}$  подзадач приблизительного размера ${\displaystyle n/p}$  на каждом этапе, тогда эффективность алгоритма «разделяй и властвуй» будет равна ${\displaystyle O(n\log _{p}n)}$ .

Алгоритмы «разделяй и властвуй» естественным образом адаптированы для выполнения многопроцессорными машинами, особенно системами с общей памятью, в которых передача данных между процессорами не должна планироваться заранее, поскольку отдельные подзадачи могут выполняться на разных процессорах.

Алгоритмы «разделяй и властвуй» естественным образом стремятся эффективно использовать кэш-память: как только подзадача достаточно мала, она и все её подзадачи могут в принципе быть решены в кэше, не обращаясь к более медленной основной памяти. Алгоритм, предназначенный для использования кэша таким образом, называется кэш-прозрачным (англ. cache-oblivious algorithm), потому что он не содержит размер кэша в качестве явного параметра^[8]. Традиционный подход к использованию кэша — блокировка, как и в оптимизации вложенных циклов^[англ.], где задача явно разделена на куски соответствующего размера, — также может использовать кэш оптимально, но только тогда, когда алгоритм настроен для конкретного размера кэша конкретной машины.

То же самое преимущество существует в отношении других иерархических систем хранения данных, таких как NUMA или виртуальная память, а также для нескольких уровней кэша: как только подзадача достаточно мала, она может быть решена в пределах данного уровня иерархии, без доступа к более высоким (более медленным) уровням.

Алгоритмы «разделяй и властвуй» естественным образом применяются в виде рекурсивных методов. В этом случае частные подзадачи, ведущие к той, которая в настоящее время решается, автоматически сохраняются в стеке вызовов процедур. Рекурсивная функция — это числовая функция числового аргумента, которая в своей записи содержит себя же.

Такие алгоритмы также могут быть применены нерекурсивной программой, которая хранит частные подзадачи в некоторой явной структуре данных, такой как стек , очередь или приоритетная очередь .Такой подход позволяет получить большую свободу в выборе подзадачи, которая должна быть решена следующей. Особенность, которая важна в некоторых приложениях — например, в методе ветвления и привязки для оптимизации функций. Этот подход также является стандартным решением в языках программирования, которые не обеспечивают поддержку рекурсивных процедур.

В рекурсивных реализациях алгоритмов «разделяй и властвуй» необходимо убедиться, что для стека рекурсии выделено достаточно памяти, иначе выполнение может завершиться неудачей из-за переполнения стека. Алгоритмы «разделяй и властвуй», которые эффективны по времени, часто имеют относительно небольшую глубину рекурсии. Например, алгоритм, быстрой сортировки может быть реализован таким образом, что он никогда не требует больше, чем ${\displaystyle \log _{2}n}$  вложенных рекурсивных вызовов для сортировки n элементов.

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

В любом рекурсивном алгоритме существует значительная свобода в выборе базовых случаев, небольших подзадач, которые решаются непосредственно для завершения рекурсии.

Выбор самых маленьких или простейших возможных базовых случаев, является более элегантным и обычно приводит к более простым программам, потому что в таком варианте меньше случаев для рассмотрения, и их легче решить. Например, быстрое преобразование Фурье может остановить рекурсию, когда входные данные являются одним образцом, а алгоритм сортировки списка быстрой сортировкой может остановиться, когда входные данные являются пустым списком; в обоих примерах есть только один базовый случай для рассмотрения, и он не требует обработки.

С другой стороны, эффективность часто повышается, если рекурсия останавливается в относительно больших базовых случаях, и они решаются нерекурсивно, что приводит к гибридному алгоритму^[англ.]. Эта стратегия позволяет избежать накладывания рекурсивных вызовов, которые работают мало или не работают, а также может позволить использовать специализированные нерекурсивные алгоритмы, которые для этих базовых случаев являются более эффективными, чем явная рекурсия. Общая процедура для простого гибридного рекурсивного алгоритма заключается в коротком замыкании базового случая, также известного как рекурсия на расстоянии вытянутой руки. В этом случае перед вызовом функции проверяется, приведёт ли следующий шаг к базовому регистру, избегая ненужного вызова функции. Поскольку алгоритм «разделяй и властвуй» в конечном итоге сводит каждый пример проблемы или подзадачи к большому числу базовых экземпляров, они часто доминируют в общей эффективности алгоритма, особенно когда накладные расходы на разделение/присоединение невелики. Причём эти соображения не зависят от того, реализуется ли рекурсия компилятором или явным стеком.

Таким образом, например, многие библиотечные применения быстрой сортировки превратятся в простой алгоритм сортировки вставки на основе цикла (или аналогичный), как только количество элементов, подлежащих сортировке, будет достаточно мало. Причём, если бы пустой список был единственным базовым случаем, то сортировка списка с ${\displaystyle n}$  записями привела бы к максимальному ${\displaystyle n}$  числу вызовов быстрых сортировок, которые ничего не сделают, но сразу же вернутся. Увеличение базовых случаев до списков размером 2 или менее приведёт к устранению большинства из этих вызовов «ничего не сделать», и в более общем случае базовый случай размером более 2 обычно используется для уменьшения доли времени, затрачиваемого на выполнение служебных функций или манипуляции стеком.

В качестве альтернативы можно использовать большие базовые случаи, которые все ещё используют алгоритм «Разделяй и властвуй», но реализуют алгоритм для предопределенного набора фиксированных размеров, где алгоритм может быть полностью развёрнут в код, который не имеет рекурсии, циклов или условных обозначений (связанных с методикой частичной оценки). Например, этот подход используется в некоторых эффективных применениях быстрого преобразования Фурье, где базовыми случаями являются развёрнутые реализации алгоритмов «разделяй и властвуй» для набора фиксированных размеров^[9]. Методы генерации исходного кода могут быть использованы для получения большого числа отдельных базовых случаев, желательных для эффективного осуществления этой стратегии.

Обобщенный вариант этой идеи известен как рекурсия «разворачивание» или «укрупнение», и были предложены различные методы для автоматизации процедуры расширения базового случая^[9].

Для некоторых задач разветвлённая рекурсия может привести к многократной оценке одной и той же подзадачи. В таких случаях, возможно, стоит определить и сохранить решения этих перекрывающихся подзадач, метод, обычно известный как мемоизация. Следуя до предела, это приводит к восходящим алгоритмам «Разделяй и властвуй», таким как динамическое программирование и разбор диаграмм.

• Основная теорема о рекуррентных соотношениях
• Декомпозируемая агрегатная функция^[англ.]
• Модель «ветвление — слияние»^[англ.]
• Математическая индукция
• MapReduce
• Эвристический алгоритм

• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.